Sum of Subarray Minimums (LeetCode 907)
You're given an array of integers arr. Look at every contiguous subarray b of arr, take its minimum value min(b), and add all of those minimums together. Because that total can get huge, return it modulo 109 + 7.
Worked Examples
arr = [3,1,2,4]17arr = [11,81,94,43,3]444444.⚖️Formal Constraints & Bounds
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
Core Insight
Do not enumerate O(N^2) subarrays. For each element arr[i], compute how many subarrays have arr[i] as their minimum using monotonic stack boundary spans: (i - prev) * (next - i) * arr[i].
Real-World Scenario & Production Applications
Risk variance analysis across streaming financial time series, minimum QoS window metrics in networking.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices with strictly increasing values -- for each element, everything still on the stack when it's pushed is a value it could be the minimum FOR.
stack = [] # indices, values strictly increasing bottom to topThe Math, Step by Step
1. The sum, counted by element instead of by subarray
The problem asks for the sum of over every contiguous subarray of arr. An array of elements has subarrays, so adding them one by one takes time or more.
The code turns the sum around. Each subarray's minimum is one element of arr, say arr[i]. So group the subarrays by the index of their minimum. Call the number of subarrays whose minimum is arr[i]. Then
This is the contribution technique: each element adds its value once for every subarray it is the minimum of.
2. Counting the subarrays of one element
Fix an index . Let left[i] be the index of the nearest element to the left that is strictly smaller than arr[i], or if there is none. Let right[i] be the index of the nearest element to the right that is smaller than or equal to arr[i], or if there is none.
A subarray from index to index has arr[i] as its claimed minimum when it contains and stays between these two walls:
has choices, and has choices. Every pair gives a different subarray, so
3. Why the walls are right
Inside the walls, no element is smaller than arr[i]. So every subarray from to has minimum arr[i]. A subarray that reaches past left[i] contains a smaller element, so its minimum is not arr[i]. A subarray that reaches right[i] contains an element that is smaller or equal. When it is smaller, the minimum is not arr[i]. When it is equal, a later copy of the same value claims the subarray, as part 4 explains.
The code finds both walls in one pass with a stack of indices whose values increase from bottom to top. When arr[i] arrives, every index on top with a value greater than or equal to arr[i] is popped. For each popped index, arr[i] is the first value to its right that is smaller or equal, so the code sets its right to i. After the pops, the index on top, if any, holds a value strictly smaller than arr[i], so it is left[i].
4. Equal values: strict on one side only
When a subarray contains its minimum value twice, only one of the two indices may count it. The code is strict on the left side (left[i] is strictly smaller) and not strict on the right side (right[i] is smaller or equal). So the rightmost copy of the minimum claims the subarray.
Take arr = [2, 2]. Its three subarrays [2], [2] and [2, 2] have minimums that add up to . With the code's walls, index 0 gets right[0] = 1 and counts subarray. Index 1 gets left[1] = -1 and counts subarrays. The total is , which is correct.
If both walls allowed equal values to pass, both indices would count [2, 2], and the total would be . If both walls stopped at equal values, neither index would count [2, 2], and the total would be .
5. Example 1 by hand
arr = [3,1,2,4], so .
arr[i] | left[i] | right[i] | |||||
|---|---|---|---|---|---|---|---|
| 0 | 3 | 1 | 1 | 1 | 1 | 3 | |
| 1 | 1 | 4 | 2 | 3 | 6 | 6 | |
| 2 | 2 | 1 | 4 | 1 | 2 | 2 | 4 |
| 3 | 4 | 2 | 4 | 1 | 1 | 1 | 4 |
The value 1 at index 1 is the minimum of 6 subarrays: is 0 or 1, and is 1, 2 or 3. The counts add up to , which is all subarrays. The sum is , the expected output.
6. Example 2 by hand
arr = [11,81,94,43,3], so .
arr[i] | left[i] | right[i] | |||
|---|---|---|---|---|---|
| 0 | 11 | 4 | 44 | ||
| 1 | 81 | 0 | 3 | 162 | |
| 2 | 94 | 1 | 3 | 94 | |
| 3 | 43 | 0 | 4 | 129 | |
| 4 | 3 | 5 | 15 |
The counts add up to subarrays. The sum is . It is smaller than , so the modulo leaves it unchanged, and the code returns 444, the expected output.
7. From the formulas to the code
| Formula | In sumSubarrayMins |
|---|---|
| nearest strictly smaller on the left, or | left = [-1] * n and left[i] = stack[-1] if stack else -1 |
| nearest smaller or equal on the right, or | right = [n] * n and right[stack.pop()] = i |
| pop while the top is greater than or equal | while stack and arr[stack[-1]] >= arr[i]: |
sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) | |
| the answer modulo | % MOD |
Every index is pushed once and popped at most once, so the pass takes time. The arrays left and right and the stack take space.
| 1 | for i in range(n): |
| 2 | while stack and arr[stack[-1]] >= arr[i]: |
| 3 | right[stack.pop()] = i |
| 4 | left[i] = stack[-1] if stack else -1 |
| 5 | stack.append(i) |
| 6 | total = sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) |
| 7 | return total % (10**9 + 7) |
Conceptual Narrative
Evaluating all O(N²) subarrays times out. Inverting the perspective—calculating how many subarrays each element serves as the minimum for—solves the problem in a single O(N) monotonic stack pass.
🧭 Conceptual Foundation & Pattern Intuition
A brute force calculates for all subarrays, which is impossible for . Instead of asking "what is the minimum of subarray ?", invert the question: If is the minimum for distinct subarrays, its total contribution to the answer is . How do we calculate ?
- Find the Previous Less Element (PLE): the first index where . can extend choices to the left.
- Find the Next Less Element (NLE): the first index where . can extend choices to the right.
- Total subarrays with as minimum: .
- Asymmetric Tie-Breaking: To avoid double-counting subarrays when duplicate numbers exist (e.g. ), use strict inequality () on one side and non-strict () on the other!
👑 The Analogy: The King of the Valley Domain
Imagine each number in the array is a king ruling a valley. A king rules in both directions as long as the neighboring peaks are taller than him. His dominion to the left stops the moment he encounters a king strictly shorter than himself (); his dominion to the right stops the moment he encounters a king shorter or equally tall (). The number of subarrays in which he is the minimum is the product of his left expansion choices and his right expansion choices .
🔑 Why It Works
One increasing stack gives both boundaries: an index popped by arr[i] gets right = i (the first smaller-or-equal value), and the index left under i is its previous strictly smaller value. Stopping at a strictly smaller value on the left and a smaller-or-equal value on the right gives every subarray exactly one minimum owner, so ties are never counted twice.
Double-counting duplicate values: Using strict inequalities on both left and right causes subarrays spanning identical minimums to be counted twice. Use
<on left and<=on right.Forgetting modulo arithmetic: Sum can grow astronomically; compute
total = (total + nums[i] * left * right) % (10**9 + 7)on every addition.Empty stack boundary off-by-one: When no smaller element exists to the left, distance is . When no smaller element exists to the right, distance is .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the sum of min(b) over every contiguous subarray b, with arr.length up to 3 * 10^4: listing all O(N²) subarrays is too slow, so count each element's share instead (Contribution Technique).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: arr[i] is the minimum of every subarray that starts in left[i] + 1 .. i and ends in i .. right[i] - 1, where left[i] is the previous strictly smaller index and right[i] the next smaller-or-equal index; the values at the indices in stack strictly increase from bottom to top.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Ties: pop while
arr[stack[-1]] >= arr[i], so the right boundary is the next smaller-or-equal value and the left one the previous strictly smaller value. The same rule on both sides counts a tied subarray twice (<on both) or never (<=on both).Modulo: the blueprint takes
% MODonce, at the end, which is safe in Python; forgetting it returns a number above 10^9 + 7. In Java or C++, use 64-bit products and reduce on every addition.Defaults:
leftstarts at-1andrightatn, so an element with no smaller value on a side reaches the end of the array.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is the Contribution Technique. Listing all subarrays is O(n squared), so I flip the question: in how many subarrays is arr[i] the minimum? It stays the minimum until the first smaller value on each side, so with left[i] and right[i] as those boundaries it owns (i minus left[i]) times (right[i] minus i) subarrays. One increasing stack finds both in a single pass: when arr[i] pops an index, arr[i] is that index's right boundary, and whatever is left under i is its left boundary. The trap is ties: I pop on greater-or-equal, so the right side stops at an equal value and the left side only at a strictly smaller one, and each subarray is counted once. Then I sum value times share and take the modulo. Each index is pushed once and popped at most once:
O(n)time,O(n)space."
Complexity & Mathematical Proof
O(N)
Look at the blueprint's two loops. The for i in range(n) loop pushes each index once with stack.append(i), and the inner while pops each index at most once (setting right[stack.pop()] = i), so across the whole loop there are at most N pushes and N pops: O(N) amortized, even though one step may pop many indices. left[i] = stack[-1] if stack else -1 is O(1) per step. The final sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) does O(1) work per index: O(N). Total: O(N) + O(N) = O(N).
O(N)
Look at the allocations: left and right hold N indices each, and stack holds at most N indices (on a strictly increasing array nothing is popped). The answer is one integer. Auxiliary space: O(N).
Derivation Progression
When arr[i] pops an index, it becomes that index's right (the first smaller-or-equal value); the index left under i is left[i] (strictly smaller). Each index enters and leaves the stack at most once.
O(1) per index: arr[i] is the minimum of every subarray starting in left[i] + 1 .. i and ending in i .. right[i] - 1.
N more O(1) steps; Python takes the modulo once at the end.
Variable Definitions
Length of input array arr
Memory Architecture & Bounds
O(1) Non-recursive loops
O(N) For the left and right arrays and the monotonic stack
O(1) One integer
Boundary Best / Worst Cases
strictly increasing array: nothing is popped until the end.
.
strictly decreasing array: every index is popped by the next one.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "sum of min(b) over all contiguous subarrays b", "modulo 109 + 7". Instead of iterating over all subarrays, invert the perspective: Contribution Counting. For each element , count the subarrays in which is the minimum, ties going to one copy only.
, . Time budget: ; the scan is about subarrays. Modulo .
Overflow outside Python: one share can reach about , far past 32 bits, so Java and C++ need 64-bit products and a modulo on every addition; Python can reduce once at the end. On a stream, right is only known when a later value pops the index, so a share can be added only once its right boundary has arrived.
Core Algorithmic State Invariants
- Every Subarray Has Exactly One Owner
Take any subarray and its smallest value; if that value appears more than once, the rightmost copy owns it: its range stops at the first smaller-or-equal value on the right, so it reaches the end of the subarray, and at a strictly smaller value on the left, so it reaches the start. Every other copy's range stops at the next equal value. So each subarray is added exactly once.
Sum of Subarray Minimums (LeetCode 907)
You're given an array of integers arr. Look at every contiguous subarray b of arr, take its minimum value min(b), and add all of those minimums together. Because that total can get huge, return it modulo 109 + 7.
Worked Examples
arr = [3,1,2,4]17arr = [11,81,94,43,3]444444.⚖️Formal Constraints & Bounds
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
Core Insight
Do not enumerate O(N^2) subarrays. For each element arr[i], compute how many subarrays have arr[i] as their minimum using monotonic stack boundary spans: (i - prev) * (next - i) * arr[i].
Real-World Scenario & Production Applications
Risk variance analysis across streaming financial time series, minimum QoS window metrics in networking.
Subproblems & Recurrence Decomposition3 Phases
Maintain a stack of indices with strictly increasing values -- for each element, everything still on the stack when it's pushed is a value it could be the minimum FOR.
stack = [] # indices, values strictly increasing bottom to topThe Math, Step by Step
1. The sum, counted by element instead of by subarray
The problem asks for the sum of over every contiguous subarray of arr. An array of elements has subarrays, so adding them one by one takes time or more.
The code turns the sum around. Each subarray's minimum is one element of arr, say arr[i]. So group the subarrays by the index of their minimum. Call the number of subarrays whose minimum is arr[i]. Then
This is the contribution technique: each element adds its value once for every subarray it is the minimum of.
2. Counting the subarrays of one element
Fix an index . Let left[i] be the index of the nearest element to the left that is strictly smaller than arr[i], or if there is none. Let right[i] be the index of the nearest element to the right that is smaller than or equal to arr[i], or if there is none.
A subarray from index to index has arr[i] as its claimed minimum when it contains and stays between these two walls:
has choices, and has choices. Every pair gives a different subarray, so
3. Why the walls are right
Inside the walls, no element is smaller than arr[i]. So every subarray from to has minimum arr[i]. A subarray that reaches past left[i] contains a smaller element, so its minimum is not arr[i]. A subarray that reaches right[i] contains an element that is smaller or equal. When it is smaller, the minimum is not arr[i]. When it is equal, a later copy of the same value claims the subarray, as part 4 explains.
The code finds both walls in one pass with a stack of indices whose values increase from bottom to top. When arr[i] arrives, every index on top with a value greater than or equal to arr[i] is popped. For each popped index, arr[i] is the first value to its right that is smaller or equal, so the code sets its right to i. After the pops, the index on top, if any, holds a value strictly smaller than arr[i], so it is left[i].
4. Equal values: strict on one side only
When a subarray contains its minimum value twice, only one of the two indices may count it. The code is strict on the left side (left[i] is strictly smaller) and not strict on the right side (right[i] is smaller or equal). So the rightmost copy of the minimum claims the subarray.
Take arr = [2, 2]. Its three subarrays [2], [2] and [2, 2] have minimums that add up to . With the code's walls, index 0 gets right[0] = 1 and counts subarray. Index 1 gets left[1] = -1 and counts subarrays. The total is , which is correct.
If both walls allowed equal values to pass, both indices would count [2, 2], and the total would be . If both walls stopped at equal values, neither index would count [2, 2], and the total would be .
5. Example 1 by hand
arr = [3,1,2,4], so .
arr[i] | left[i] | right[i] | |||||
|---|---|---|---|---|---|---|---|
| 0 | 3 | 1 | 1 | 1 | 1 | 3 | |
| 1 | 1 | 4 | 2 | 3 | 6 | 6 | |
| 2 | 2 | 1 | 4 | 1 | 2 | 2 | 4 |
| 3 | 4 | 2 | 4 | 1 | 1 | 1 | 4 |
The value 1 at index 1 is the minimum of 6 subarrays: is 0 or 1, and is 1, 2 or 3. The counts add up to , which is all subarrays. The sum is , the expected output.
6. Example 2 by hand
arr = [11,81,94,43,3], so .
arr[i] | left[i] | right[i] | |||
|---|---|---|---|---|---|
| 0 | 11 | 4 | 44 | ||
| 1 | 81 | 0 | 3 | 162 | |
| 2 | 94 | 1 | 3 | 94 | |
| 3 | 43 | 0 | 4 | 129 | |
| 4 | 3 | 5 | 15 |
The counts add up to subarrays. The sum is . It is smaller than , so the modulo leaves it unchanged, and the code returns 444, the expected output.
7. From the formulas to the code
| Formula | In sumSubarrayMins |
|---|---|
| nearest strictly smaller on the left, or | left = [-1] * n and left[i] = stack[-1] if stack else -1 |
| nearest smaller or equal on the right, or | right = [n] * n and right[stack.pop()] = i |
| pop while the top is greater than or equal | while stack and arr[stack[-1]] >= arr[i]: |
sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) | |
| the answer modulo | % MOD |
Every index is pushed once and popped at most once, so the pass takes time. The arrays left and right and the stack take space.
| 1 | for i in range(n): |
| 2 | while stack and arr[stack[-1]] >= arr[i]: |
| 3 | right[stack.pop()] = i |
| 4 | left[i] = stack[-1] if stack else -1 |
| 5 | stack.append(i) |
| 6 | total = sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) |
| 7 | return total % (10**9 + 7) |
Conceptual Narrative
Evaluating all O(N²) subarrays times out. Inverting the perspective—calculating how many subarrays each element serves as the minimum for—solves the problem in a single O(N) monotonic stack pass.
🧭 Conceptual Foundation & Pattern Intuition
A brute force calculates for all subarrays, which is impossible for . Instead of asking "what is the minimum of subarray ?", invert the question: If is the minimum for distinct subarrays, its total contribution to the answer is . How do we calculate ?
- Find the Previous Less Element (PLE): the first index where . can extend choices to the left.
- Find the Next Less Element (NLE): the first index where . can extend choices to the right.
- Total subarrays with as minimum: .
- Asymmetric Tie-Breaking: To avoid double-counting subarrays when duplicate numbers exist (e.g. ), use strict inequality () on one side and non-strict () on the other!
👑 The Analogy: The King of the Valley Domain
Imagine each number in the array is a king ruling a valley. A king rules in both directions as long as the neighboring peaks are taller than him. His dominion to the left stops the moment he encounters a king strictly shorter than himself (); his dominion to the right stops the moment he encounters a king shorter or equally tall (). The number of subarrays in which he is the minimum is the product of his left expansion choices and his right expansion choices .
🔑 Why It Works
One increasing stack gives both boundaries: an index popped by arr[i] gets right = i (the first smaller-or-equal value), and the index left under i is its previous strictly smaller value. Stopping at a strictly smaller value on the left and a smaller-or-equal value on the right gives every subarray exactly one minimum owner, so ties are never counted twice.
Double-counting duplicate values: Using strict inequalities on both left and right causes subarrays spanning identical minimums to be counted twice. Use
<on left and<=on right.Forgetting modulo arithmetic: Sum can grow astronomically; compute
total = (total + nums[i] * left * right) % (10**9 + 7)on every addition.Empty stack boundary off-by-one: When no smaller element exists to the left, distance is . When no smaller element exists to the right, distance is .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the sum of min(b) over every contiguous subarray b, with arr.length up to 3 * 10^4: listing all O(N²) subarrays is too slow, so count each element's share instead (Contribution Technique).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: arr[i] is the minimum of every subarray that starts in left[i] + 1 .. i and ends in i .. right[i] - 1, where left[i] is the previous strictly smaller index and right[i] the next smaller-or-equal index; the values at the indices in stack strictly increase from bottom to top.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Ties: pop while
arr[stack[-1]] >= arr[i], so the right boundary is the next smaller-or-equal value and the left one the previous strictly smaller value. The same rule on both sides counts a tied subarray twice (<on both) or never (<=on both).Modulo: the blueprint takes
% MODonce, at the end, which is safe in Python; forgetting it returns a number above 10^9 + 7. In Java or C++, use 64-bit products and reduce on every addition.Defaults:
leftstarts at-1andrightatn, so an element with no smaller value on a side reaches the end of the array.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"This is the Contribution Technique. Listing all subarrays is O(n squared), so I flip the question: in how many subarrays is arr[i] the minimum? It stays the minimum until the first smaller value on each side, so with left[i] and right[i] as those boundaries it owns (i minus left[i]) times (right[i] minus i) subarrays. One increasing stack finds both in a single pass: when arr[i] pops an index, arr[i] is that index's right boundary, and whatever is left under i is its left boundary. The trap is ties: I pop on greater-or-equal, so the right side stops at an equal value and the left side only at a strictly smaller one, and each subarray is counted once. Then I sum value times share and take the modulo. Each index is pushed once and popped at most once:
O(n)time,O(n)space."
Complexity & Mathematical Proof
O(N)
Look at the blueprint's two loops. The for i in range(n) loop pushes each index once with stack.append(i), and the inner while pops each index at most once (setting right[stack.pop()] = i), so across the whole loop there are at most N pushes and N pops: O(N) amortized, even though one step may pop many indices. left[i] = stack[-1] if stack else -1 is O(1) per step. The final sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) does O(1) work per index: O(N). Total: O(N) + O(N) = O(N).
O(N)
Look at the allocations: left and right hold N indices each, and stack holds at most N indices (on a strictly increasing array nothing is popped). The answer is one integer. Auxiliary space: O(N).
Derivation Progression
When arr[i] pops an index, it becomes that index's right (the first smaller-or-equal value); the index left under i is left[i] (strictly smaller). Each index enters and leaves the stack at most once.
O(1) per index: arr[i] is the minimum of every subarray starting in left[i] + 1 .. i and ending in i .. right[i] - 1.
N more O(1) steps; Python takes the modulo once at the end.
Variable Definitions
Length of input array arr
Memory Architecture & Bounds
O(1) Non-recursive loops
O(N) For the left and right arrays and the monotonic stack
O(1) One integer
Boundary Best / Worst Cases
strictly increasing array: nothing is popped until the end.
.
strictly decreasing array: every index is popped by the next one.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "sum of min(b) over all contiguous subarrays b", "modulo 109 + 7". Instead of iterating over all subarrays, invert the perspective: Contribution Counting. For each element , count the subarrays in which is the minimum, ties going to one copy only.
, . Time budget: ; the scan is about subarrays. Modulo .
Overflow outside Python: one share can reach about , far past 32 bits, so Java and C++ need 64-bit products and a modulo on every addition; Python can reduce once at the end. On a stream, right is only known when a later value pops the index, so a share can be added only once its right boundary has arrived.
Core Algorithmic State Invariants
- Every Subarray Has Exactly One Owner
Take any subarray and its smallest value; if that value appears more than once, the rightmost copy owns it: its range stops at the first smaller-or-equal value on the right, so it reaches the end of the subarray, and at a strictly smaller value on the left, so it reaches the start. Every other copy's range stops at the next equal value. So each subarray is added exactly once.