907. Sum of Subarray Minimums - Explanation

1. Brute Force

Intuition

For each subarray, we need to find its minimum element and add it to the total sum. The straightforward approach is to enumerate all possible subarrays by their start and end positions, tracking the running minimum as we extend each subarray.

Algorithm

Initialize res = 0 to store the sum of minimums.
For each starting index i:
- Initialize minVal = arr[i].
- For each ending index j from i to n - 1:
  - Update minVal = min(minVal, arr[j]).
  - Add minVal to res (modulo 10^9 + 7).
Return res.

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

        for i in range(n):
            minVal = arr[i]
            for j in range(i, n):
                minVal = min(minVal, arr[j])
                res = (res + minVal) % MOD

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Monotonically Increasing Stack (Two Pass)

Intuition

Instead of computing minimums for each subarray, we can ask: for each element, how many subarrays is it the minimum of? An element arr[i] is the minimum of all subarrays that start after the previous smaller element and end before the next smaller element. A monotonically increasing stack helps us efficiently find these boundaries.

Algorithm

Use a stack to find prevSmaller[i]: the index of the previous smaller element (or -1 if none).
Use another stack pass to find nextSmaller[i]: the index of the next smaller or equal element (or n if none). We use "smaller or equal" on one side to avoid double counting.
For each element at index i:
- left = i - prevSmaller[i] is the count of valid starting positions.
- right = nextSmaller[i] - i is the count of valid ending positions.
- Add arr[i] * left * right to the result.
Return res modulo 10^9 + 7.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)

        # Compute previous smaller
        prev_smaller = [-1] * n
        stack = []
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            prev_smaller[i] = stack[-1] if stack else -1
            stack.append(i)

        # Compute next smaller
        next_smaller = [n] * n
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            next_smaller[i] = stack[-1] if stack else n
            stack.append(i)

        res = 0
        for i in range(n):
            left = i - prev_smaller[i]
            right = next_smaller[i] - i
            res = (res + arr[i] * left * right) % MOD

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Monotonically Increasing Stack (One Pass)

Intuition

We can combine finding the previous smaller and next smaller into a single pass. By adding sentinel values (negative infinity) at both ends of the array, we ensure every element gets processed. When we pop an element from the stack upon finding a smaller value, we immediately know both its left boundary (from the new stack top) and right boundary (the current index).

Algorithm

Pad the array with negative infinity at both ends.
Maintain a stack of (index, value) pairs.
For each element in the padded array:
- While the stack is not empty and the current element is smaller than the stack top:
  - Pop the top element (index j, value m).
  - left = j - stack_top_index (or j + 1 if stack is empty).
  - right = i - j.
  - Add m * left * right to the result.
- Push the current (index, value) onto the stack.
Return res modulo 10^9 + 7.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        res = 0
        arr = [float("-inf")] + arr + [float("-inf")]
        stack = []  # (index, num)

        for i, n in enumerate(arr):
            while stack and n < stack[-1][1]:
                j, m = stack.pop()
                left = j - stack[-1][0] if stack else j + 1
                right = i - j
                res = (res + m * left * right) % MOD
            stack.append((i, n))

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Monotonically Increasing Stack (Optimal)

Intuition

We can eliminate the sentinel values by handling the edge cases explicitly. Instead of padding the array, we iterate one position past the end and use a conditional check to treat the out-of-bounds position as having a smaller value than any element. This triggers final processing of remaining stack elements.

Algorithm

Initialize an empty stack and res = 0.
Iterate from i = 0 to n (inclusive):
- While the stack is not empty and (we're at the end OR arr[i] < arr[stack_top]):
  - Pop index j from the stack.
  - left = j - stack_top (or j + 1 if stack is empty).
  - right = i - j.
  - Add arr[j] * left * right to res.
- Push i onto the stack.
Return res modulo 10^9 + 7.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        stack = []
        res, n = 0, len(arr)

        for i in range(n + 1):
            while stack and (i == n or arr[i] < arr[stack[-1]]):
                j = stack.pop()
                left = j - (stack[-1] if stack else -1)
                right = i - j
                res = (res + arr[j] * left * right) % MOD
            stack.append(i)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Dynamic Programming + Stack

Intuition

We can think of this problem dynamically. Let dp[i] represent the sum of minimums of all subarrays ending at index i. When we add element arr[i], we need to consider: for subarrays where arr[i] is not the minimum, we can reuse previously computed values; for subarrays where arr[i] is the minimum, we count how many such subarrays exist. The stack helps us find where arr[i] stops being the minimum.

Algorithm

Initialize dp array and an empty stack.
For each index i:
- Pop elements from the stack while arr[stack_top] > arr[i].
- Let j be the stack top after popping (or -1 if empty). This is the index of the previous smaller or equal element.
- dp[i] = dp[j] + arr[i] * (i - j):
  - dp[j] accounts for subarrays ending before j where arr[i] is not the minimum.
  - arr[i] * (i - j) accounts for subarrays from positions j+1 to i where arr[i] is the minimum.
- Add dp[i] to res and push i onto the stack.
Return res modulo 10^9 + 7.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        dp = [0] * n
        stack, res = [], 0

        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            j = stack[-1] if stack else -1
            dp[i] = (dp[j] if j != -1 else 0) + arr[i] * (i - j)
            dp[i] %= MOD
            res = (res + dp[i]) % MOD
            stack.append(i)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Double Counting with Duplicate Elements

When there are duplicate values in the array, using strict less-than (<) on both sides when finding previous and next smaller elements causes the same subarray to be counted multiple times. The solution is to use strict less-than (<) on one side and less-than-or-equal (<=) on the other side to ensure each subarray is counted exactly once.

Integer Overflow in Contribution Calculation

The contribution formula arr[i] * left * right can overflow a 32-bit integer when the array is large. With n up to 30,000 and values up to 30,000, the product can reach approximately 2.7 * 10^13. Always use 64-bit integers for the multiplication and apply the modulo operation at each step.

Incorrect Boundary Initialization

When no previous smaller element exists, prevSmaller[i] should be -1 (not 0), representing an imaginary boundary before the array. Similarly, when no next smaller element exists, nextSmaller[i] should be n (not n-1). Using wrong boundary values leads to incorrect counts for subarrays starting at the beginning or ending at the end of the array.

Forgetting to Apply Modulo Operation

The problem requires returning the result modulo 10^9 + 7. A common mistake is only applying modulo at the final return statement. Since intermediate sums can overflow even with 64-bit integers after many additions, modulo should be applied after each addition to the result to keep values within bounds.