visual walkthrough
Sum of Subarray Minimums
Counts each element's contribution using previous/next smaller elements.
The idea
Flip the question: instead of finding the minimum of every subarray, count how many subarrays each number is the minimum of.
A monotonic stack finds the nearest smaller value on each side, which bounds where those subarrays can start and end.
Complexity
| approach | time | space |
|---|---|---|
| Every subarray | O(n²) | O(1) |
| Contribution with monotonic stacks | O(n) | O(n) |