< Back





907. Sum of Subarray Minimums

Pretty difficult question, actually. We use a monotonically increasing stack to keep track of
minimum values we encounter in each subarray, but determining how to find the number of subarrays a
particular minimum applies to is pretty difficult.

What we have to realize is that, given some range, l and r, the number of subarrays that the minimum
value applies to is:

  (m - l) * (r - m)

where m is in the index of the current minimum, l is the index of the previous minimum, and r is the
index of the next minimum. To determine the contribution of the current minimum to the answer:

  arr[m] * (m - l) * (r - m)

So we traverse the array from left to right, and maintain a monotonically increasing stack. When we
need to manage the monotonically increasing stack, we pop off a value, known as the middle. We
calculate l, the top of the stack and most recent minimum - otherwise -1 if the stack is empty. We
calculate the count and contribution and add it to the answer for the current minimum. We then push
the new minimum to the stack.

We make sure to continue to process the stack and array until i == len(arr) - once i == len(arr), we
need to continue to pop values from the stack until all minimums are processed.

The solution is as follows:


  class Solution:
      def sumSubarrayMins(self, arr: List[int]) -> int:
          stack = []
          n, ans = len(arr), 0

          for i in range(n + 1):
              while stack and (i == n or arr[stack[-1]] >= arr[i]):
                  m = stack.pop()
                  l = -1 if not stack else stack[-1]
                  r = i
                  ans += arr[m] * (m - l) * (r - m)

              stack.append(i)

          return ans % ((10**9) + 7)


_ Time Complexity:

  O(n) - We inspect all elements in the array once.

_ Space Complexity:

  O(n) - We maintain a monotonically increasing stack.