Problem Statement in English

You’re given an array of integers arr. Find the sum of min(b) where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.

Approach

The idea here is that every element in the array will be the minimum of some subarray(s).

We just need to find out how many subarrays have that element as the minimum. This can be thought of as finding the “dominance” of that element. The dominance must include upto how many indices forward, and upto how many indices backward, that element is the minimum.

After that we can just multiply the value of the element with the number of subarrays that have it as the minimum, and add that to our result.

But how can we do this?

Well, we can use a monotonic stack to find the next smaller element for each element in the array. This will give us the forward extension of the dominance. We can also use the same stack to find the previous smaller element for each element in the array, which will give us the backward extension of the dominance.

Then we can just multiply the forward extension, the backward extension, and the value of the element to get the contribution of that element to the final result.

And we’re done!

Solution in Python


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 1000_000_007

        res = 0
        stack = []

        for i, v in enumerate(arr):
            while stack and stack[-1][1] > v:
                index, oldValue = stack.pop()
                # forward extension of old stack top
                forward = (i - index)
                # backward extension of old stack top
                dominatesTill = -1 if not stack else stack[-1][0]
                backward = (index - dominatesTill)

                res += forward * backward * oldValue

            stack.append((i, v))

        l = len(arr)
        while stack:
            i,v = stack.pop()
            # forward extension of old stack top
            forward = (l - i)
            # backward extension of old stack top
            dominatesTill = -1 if not stack else stack[-1][0]
            backward = (i - dominatesTill)

            res += forward * backward * v

        return res % MOD

Complexity

  • Time: $O(n)$
    Since we are iterating through the array once, and each element is pushed and popped from the stack at most once.

  • Space: $O(n)$
    Since we are using a stack to keep track of the indices and values, in the worst case, we might have to store all the elements in the stack.

Mistakes I Made

I had to look this one up :(

And we are done.