907. Sum of Subarray Minimums

907

MediumMonotonic Stack and Monotonic QueueMonotonic increasing stack computing each element's span as a subarray minimumSum of minimums via contribution counting

Sum of Subarray Minimums

Given an array arr, consider every contiguous subarray and take the minimum of each. Return the sum of all those minimums, modulo 10^9 + 7.

Open official problem prompt ↗

In plain English

Add up the minimum of every contiguous subarray without enumerating the quadratically many subarrays, returning the result modulo 10^9 + 7.

Picture it like this

Rather than paying attention to each subarray, ask every element: 'For how many windows are you the shortest person in the room?' Multiply that count by your height and add up everyone's contribution.

Example

Input: arr = [3, 1, 2, 4]
Output: 17
Why: The subarray minimums are 3,1,2,4,1,1,2,1,1,1 and they sum to 17.

Constraints

1 <= arr.length <= 3 * 10^41 <= arr[i] <= 3 * 10^4

Pattern lesson

See the pattern, then code

Sum of minimums via contribution counting

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Each element arr[i] contributes arr[i] once for every subarray in which it is the minimum. That count equals (distance to the previous strictly smaller element) times (distance to the next smaller-or-equal element). A monotonic stack finds both boundaries in one pass.

New words, made simpleKnow these before the algorithm

Contribution counting: Summing a total by asking how much each element adds across all structures, instead of visiting each structure.
Previous less element: Nearest index to the left with a strictly smaller value; bounds how far left an element stays the minimum.
Next less-or-equal element: Nearest index to the right whose value is <= the current one; bounds the right side while breaking ties to avoid double counting.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all subarrays

Up to ~4.5*10^8 operations at n=3*10^4; too slow and times out.

For every start index, extend the end and track the running minimum.

Time O(n^2)Space O(1)

Best choiceMonotonic stack contribution

Every index is pushed and popped once, yielding linear time.

For each element compute how many subarrays it is the minimum of using previous-smaller and next-smaller-or-equal boundaries.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack holds indices whose values are non-decreasing from bottom to top; each element's minimum-region is finalized exactly when it is popped.

Why this is correct

Reasoning

An element arr[mid] is the minimum of a subarray iff the subarray lies entirely between its previous strictly smaller element and its next smaller-or-equal element. There are (mid - left) choices for the left endpoint and (right - mid) for the right, so arr[mid] contributes arr[mid] * (mid - left) * (right - mid). Using strictly-smaller on the left and smaller-or-equal on the right makes tie-breaking consistent, so subarrays with duplicate minimums are counted exactly once. The -infinity sentinel at index n forces every remaining element to be popped and finalized.

The algorithm in three movesSay these aloud before coding

1Maintain an increasing stack of indices and iterate with a virtual -infinity sentinel at index n

1 is the min of 6 subarrays: (1-(-1))*(4? boundary) ... left=-1, right past end

2When the incoming value is <= the value at the stack top, that top's right boundary is found — pop it

3 contributes 3*1*1=3; 2 contributes 2*1*2=4; 4 contributes 4*1*1=4

3For the popped index mid, let left be the new stack top (previous smaller); add arr[mid] * (mid - left) * (i - mid)

1 contributes 1*2*3=6; total 3+6+4+4=17

4Push the current index; return the running total modulo 10^9 + 7

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readcur=3

2 · AskStack empty?

3 · Update statestack=[]

4 · ResultPush 0. stack=[0]

Key takeaway

For value 1 at index 1, it is the minimum of every subarray spanning from index 0..1 on the left to index 1..3 on the right.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-6Setup with modulus and sentinel loop
Iterating to n inclusive lets a virtual -infinity flush the stack so no element is left unfinalized.
2
Lines 7Virtual sentinel value
Treating index n as -infinity guarantees the final while-loop empties the stack.
3
Lines 8-11Finalize a minimum region
Popping on arr[top] >= cur marks cur as the next smaller-or-equal boundary; left is the previous smaller, and the product counts all subarrays where arr[mid] is the minimum.
4
Lines 12-13Push and reduce
Push the current index for later boundaries; the modulus is applied once at the end for correctness within Python's big integers.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element returns that element
All equal elements: the >= / strict split still counts each subarray exactly once
Strictly increasing array: each element is the minimum only of subarrays starting at it
Large arrays require the modulo to keep the result in range

Common beginner mistakes

Using the same strict comparison on both sides double-counts subarrays with duplicate minimums
Forgetting the sentinel leaves elements on the stack whose contribution is never added
Applying the modulo only at the end is fine in Python but overflows in fixed-width languages — reduce per step there
Confusing 'minimum' boundaries (smaller elements) with 'maximum' boundaries (larger elements)

Check your understanding

Why use strictly-smaller on the left but smaller-or-equal on the right?

Sum of Subarray Minimums

Sum of Subarray Minimums

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue