Sum of Subarray Minimums
Return the sum of the minimum element over every subarray, modulo 1e9+7.
- 1 <= arr.length <= 3 * 10⁴
- 1 <= arr[i] <= 3 * 10⁴
Intuition
Sum of subarray minimums adds up the minimum of every contiguous subarray. There are O(n²) subarrays, so enumerating them is far too slow.
The reframing that makes this tractable inverts the question. Instead of asking what is the minimum of each subarray, ask:
- For each element, how many subarrays have it as their minimum? Then the answer is the sum of element × count over all elements.
That count is determined by how far the element's influence extends. It is the minimum of every subarray that spans it without including anything smaller — so the boundaries are the nearest smaller element on each side.
If the nearest smaller element to the left is at distance left and to the right at distance right, the element is the minimum of exactly left × right subarrays — one for each choice of start and end within its range.
A monotonic increasing stack finds both boundaries in linear time, one pass per side, or both in a single pass with care.
Duplicate values are the trap. If both sides use the same strict comparison, subarrays containing two equal minimums get counted twice. The fix is asymmetry: use strictly smaller on one side and smaller-or-equal on the other. That assigns each subarray to exactly one of its tied minimums.
Getting that wrong produces answers that are correct on arrays with distinct values and wrong the moment duplicates appear — which is why it survives casual testing.
The result requires modulo 10⁹+7, applied as the sum accumulates rather than at the end.
Each element is pushed and popped once, giving O(n) time and O(n) space.
Contribution counting. Instead of enumerating subarrays, ask how many of them each element is the minimum of — that's (i - pse) * (nse - i), the choices of left and right boundary within its span. The asymmetric strictness (>= on one side, > on the other) is what stops equal values double-counting.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Invert the question
Rather than finding each subarray's minimum, ask how many subarrays each element is the minimum of. The answer is then a weighted sum.
Find the nearest smaller elements
An element is the minimum of every subarray spanning it without anything smaller, so its boundaries are the nearest smaller element on each side.
Multiply the two distances
With left and right as the distances to those boundaries, the element is the minimum of exactly left × right subarrays — one per start and end choice.
Use a monotonic stack
An increasing stack finds both boundaries in linear time, popping elements as a smaller value arrives.
Break ties asymmetrically
Use strictly smaller on one side and smaller-or-equal on the other. Identical comparisons double-count subarrays with tied minimums.
Apply the modulus while summing
Take the result modulo 10^9+7 as it accumulates, not at the end — the running total overflows well before the largest inputs.
Cost of the approach
Each element is pushed and popped once, giving O(n) time and O(n) space in place of the O(n²) enumeration.
Solution & live demo
Common pitfalls
Using the same strictness in both passes
while st and arr[st[-1]] >= arr[i]: # in both loops
# previous smaller: >= # next smaller: >
With duplicates, symmetric comparisons let two equal elements each claim the subarrays between them, so those are counted twice. Making one side strict assigns every subarray to exactly one representative.
Enumerating subarrays directly
for i in range(n):
for j in range(i, n):
total += min(arr[i:j+1])total += arr[i] * (i - pse[i]) * (nse[i] - i)
That's O(n³), or O(n²) with a running minimum — both too slow at n = 30,000. Contribution counting is linear because each element's span is found once by the stack.
Applying the modulo only at the end
total += arr[i] * (i - pse[i]) * (nse[i] - i) return total % MOD
total = (total + arr[i] * (i - pse[i]) % MOD * (nse[i] - i)) % MOD
Python's big integers tolerate it, but in C++/Java the product of a value and two spans near 30,000 overflows a 64-bit int across the whole sum. Reduce as you accumulate.
Edge cases
The strict/non-strict asymmetry is exactly what stops double counting here — the case worth hand-checking.
Every element is the minimum only of subarrays starting at itself, so left is always 1.
One subarray, so the answer is that element.
Sums exceed 64-bit range for large inputs, so apply the modulus as you accumulate.