Sum of Subarray Minimums Solution

Problem

Given an integer array, find the sum of the minimum value of every contiguous subarray. Because the answer can be enormous, return it modulo 10⁹ + 7.

For example, the array [3, 1, 2, 4] has 10 subarrays:

Input: arr = [3, 1, 2, 4]
Output: 17
Explanation: minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1 — they sum to 17

Intuition

Instead of finding the minimum of each subarray separately, flip the question: for each element, count how many subarrays have that element as their minimum, then multiply by its value. Summing those contributions gives the answer without ever scanning subarrays.

To count subarrays for element arr[i], find how far left and right you can extend while arr[i] stays the minimum. A monotonic stack computes both distances in O(n) total.

Approach 1 — Brute Force

For each possible left endpoint, track the running minimum as you extend the right endpoint one step at a time. The minimum can only stay the same or decrease, so no extra scan is needed.

Initialize a running total and iterate over all left endpoints.
At each left endpoint, set the current minimum to arr[left].
Extend the right endpoint from left to the end, updating the minimum each step.
Add the current minimum to the total and apply the modulus.

1def sumSubarrayMins(arr: list[int]) -> int:
2    MOD = 10**9 + 7
3    n = len(arr)
4    total = 0
5    for left in range(n):
6        current_min = arr[left]
7        for right in range(left, n):
8            current_min = min(current_min, arr[right])
9            total = (total + current_min) % MOD
10    return total

Time: O(n²) — every pair of (left, right) endpoints is visited once.
Space: O(1) — only a constant number of variables needed beyond the input.

Approach 2 — Monotonic Stack (Contribution Counting)

For each index i, compute left[i] — the number of subarrays ending at i where arr[i] is the minimum — and right[i] — the number of subarrays starting at i where arr[i] is the minimum. The element's total contribution is arr[i] * left[i] * right[i].

Use a monotonic stack to find the previous strictly-smaller element for left and the next smaller-or-equal element for right. This asymmetry is the key to avoiding double-counting when duplicate values appear.

Pass left to right with a stack of indices, popping while the stack top is ≥ the current element. left[i] equals the distance to the surviving stack top (or i + 1 if the stack is empty).
Pass right to left with a fresh stack, popping while the stack top is > the current element. right[i] equals the distance to the surviving stack top (or n - i if the stack is empty).
Sum arr[i] * left[i] * right[i] over all indices, modulo 10⁹ + 7.

1def sumSubarrayMins(arr: list[int]) -> int:
2    MOD = 10**9 + 7
3    n = len(arr)
4    left = [0] * n
5    right = [0] * n
6    stack = []  # indices, bottom-to-top is increasing in arr value
7
8    for i in range(n):
9        # pop elements that are no longer "previous strictly smaller"
10        while stack and arr[stack[-1]] >= arr[i]:
11            stack.pop()
12        left[i] = i - stack[-1] if stack else i + 1
13        stack.append(i)
14
15    stack = []
16    for i in range(n - 1, -1, -1):
17        # pop elements that are no longer "next smaller or equal"
18        while stack and arr[stack[-1]] > arr[i]:
19            stack.pop()
20        right[i] = stack[-1] - i if stack else n - i
21        stack.append(i)
22
23    return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD

Time: O(n) — each index is pushed and popped at most once per stack pass.
Space: O(n) — the stack holds at most n indices at a time, plus the left/right arrays.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	n ≤ 3,000 or for verifying a solution
Monotonic Stack	O(n)	O(n)	Production — required for n up to 30,000

Common Mistakes

Symmetric tie-breaking causes double counting. Using strictly-smaller on both sides (popping when >= in both passes) makes two equal adjacent elements each claim the full shared range. Use >= on the left pass and > on the right pass, or vice versa, so exactly one element wins the tie.
Storing the index instead of the distance. left[i] should be the count of valid left endpoints (a distance), not the index of the previous smaller element. The distance is i - prev_index, not prev_index alone.
Omitting the modulus on the final multiplication. arr[i] * left[i] * right[i] can exceed 10¹⁸ in Java and C++ even before summing; cast to long/long long and apply % MOD inside the loop, not just at the very end.
Forgetting the empty-stack case for left[i]. When no previous smaller element exists, the left boundary is the virtual index -1, making left[i] = i - (-1) = i + 1, not i.
Trying to extend the brute force with early termination. Unlike two-pointer problems, you cannot skip subarrays once the minimum hits a floor; every subarray still needs its minimum counted.

Sum of Subarray Minimums — Solution