Sum of Subarray Minimums
Add up min(b) over every contiguous subarray b, in linear time, by counting with a monotonic stack how many subarrays each value is the minimum of.
Problem Understanding
Sum of Subarray Minimums: given an array of integers arr, find the sum of min(b) for every contiguous subarray b, modulo 10⁹ + 7.
Examples: [3,1,2,4] → 17 (minimums 3, 1, 2, 4, 1, 1, 2, 1, 1, 1); [11,81,94,43,3] → 444.
The Intuition: Count What Each Value Is the Minimum Of
There are O(n²) subarrays, but only n values that can be a minimum. Flip the question: for each value, how many subarrays is it the minimum of?
- Left reach: up to the nearest strictly smaller value on its left.
- Right reach: up to the nearest smaller-or-equal value on its right.
- Count: (choices of start) × (choices of end) =
(i - L) × (R - i).
Both nearest-smaller boundaries come out of one monotonic stack pass, the same structure as Largest Rectangle in Histogram and Daily Temperatures.
Interactive Walkthrough
TINTED = WHERE THE POPPED VALUE IS THE MINIMUM
EMPTY STACK
arr
i
0
1
2
3
stack (bottom → top): value, index below
EMPTY
subarrays
:
added
:
total
0
For each value, count the subarrays it is the minimum of. The stack keeps indices with increasing values
Next
Read arr[0] = 3
arr
When a value is popped, the stretch of the array where it is the minimum is tinted and its contribution is added. Try Ties to see equal values counted once.
Dry Run Table
Input: [3,1,2,4].
| i | Pops | left | right | Added | Total |
|---|---|---|---|---|---|
| 1 | 3 (index 0) | -1 | 1 | 3 × 1 × 1 = 3 | 3 |
| 4 (end) | 4 (index 3) | 2 | 4 | 4 × 1 × 1 = 4 | 7 |
| 4 (end) | 2 (index 2) | 1 | 4 | 2 × 1 × 2 = 4 | 11 |
| 4 (end) | 1 (index 1) | -1 | 4 | 1 × 2 × 3 = 6 | 17 |
Answer: 17.
The Solution Template
One pass with a sentinel at i = n. JavaScript and TypeScript use BigInt for the running sum, since the products can exceed 2⁵³ before the modulo.
Sum of Subarray Minimums Code
1var sumSubarrayMins = function(arr) {2 const MOD = 1_000_000_007n;3 const n = arr.length;4 const stack = [];5 let total = 0n;6 for (let i = 0; i <= n; i++) {7 while (stack.length && (i === n || arr[stack[stack.length - 1]] >= arr[i])) {8 const mid = stack.pop();9 const left = stack.length ? stack[stack.length - 1] : -1;10 total += BigInt(arr[mid] * (mid - left) * (i - mid));11 }12 stack.push(i);13 }14 return Number(total % MOD);15};
Edge Cases & Common Mistakes
- Duplicates: use
>=when popping (or>on the other side), never the same comparison on both sides, or ties are double counted. - Overflow: take the modulo as you go in Java/C++/C, or use 64-bit math.
- Leftover stack: flush it with i = n so every value is counted.
- One element: the answer is that element.
- Brute force: O(n²) with a running minimum works for small n but times out at 3 × 10⁴.
Summary
Each value contributes value × (distance to the nearest smaller on the left) × (distance to the nearest smaller-or-equal on the right). A monotonic stack finds both distances as it pops. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet