Builds on Histogram Stack, which you haven’t finished yet.
Contribution Technique (Sum over All Subarrays via Each Element's Share)
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.
Contribution Technique
all subarrays ➔ element i is the minimum of (i - left) × (right - i) of them ➔ sum of sharesO(n^2).| 1 | def sum_subarray_mins(arr: list[int]) -> int: |
| 2 | """Sum of Subarray Minimums: add up each element's share as the minimum. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | MOD = 10**9 + 7 |
| 6 | n = len(arr) |
| 7 | left = [-1] * n # Index of the previous strictly smaller element |
| 8 | right = [n] * n # Index of the next smaller-or-equal element |
| 9 | stack: list[int] = [] # Indices with increasing values from bottom to top |
| 10 | |
| 11 | # 1. Visit Every Index Left To Right: |
| 12 | # One pass finds both walls for every index, since each index's walls only depend on values already seen or seen as they arrive. |
| 13 | for i in range(n): |
| 14 | # 2. Resolve Every Index That arr[i] Beats Or Ties: |
| 15 | # While the top of the stack is not strictly smaller than arr[i], arr[i] is the first value to its right that is smaller or equal, so pop it and record i as its right wall. The >= (not >) is what sends a tie's right wall to the later copy. |
| 16 | while stack and arr[stack[-1]] >= arr[i]: |
| 17 | right[stack.pop()] = i # arr[i] is the first value <= the popped one |
| 18 | # 3. Record The Left Wall And Push i: |
| 19 | # After the pops above, whatever remains on top is strictly smaller than arr[i], so it is arr[i]'s left wall; i then joins the stack to serve as a future right wall. |
| 20 | left[i] = stack[-1] if stack else -1 # Top is strictly smaller |
| 21 | stack.append(i) |
| 22 | |
| 23 | # 4. Add Up Every Index's Share: |
| 24 | # arr[i] is the minimum of (i - left[i]) * (right[i] - i) subarrays, so multiplying and summing counts every subarray's minimum exactly once. |
| 25 | return sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) % MOD |
stack strictly increase from bottom to top, so the index under i is its previous strictly smaller element and the index that pops i is its next smaller-or-equal one.Instead of listing every subarray, ask how many subarrays have arr[i] as their minimum: it stays the minimum until the first smaller value on each side, at left[i] and right[i]. That gives (i - left[i]) * (right[i] - i) subarrays, and one increasing stack finds both boundaries as values are popped. For equal values, stop at a strictly smaller value on one side and a smaller-or-equal value on the other (the >= in the pop), or subarrays with ties are counted twice.
See it run
Contribution Technique, step by step
stack []left [-1, -1, -1, -1]right [4, 4, 4, 4]
The top row is arr. The column number is the index. The bottom row is the stack: the left cell is the bottom, each cell holds an index, and a blank cell is an unused slot. A wall of -1, or a wall equal to the length of arr, has no cell, because it is outside arr.
ithe index being read nowpoppedthe index taken off the stack, whose right wall is written nowleft wallthe index in left[i], a strictly smaller value on the leftright wallthe index in right[i], a smaller or equal value on the rightpushedthe index that was just pushed
Start: stack is empty, every left is -1 and every right is 4.
Gotcha 1 of 3
- The trap
Gotcha 1: Stopping at a strictly smaller value on both sides
Mistakefor i in range(n - 1, -1, -1): while stack and arr[stack[-1]] >= arr[i]: stack.pop() right[i] = stack[-1] if stack else nFixwhile stack and arr[stack[-1]] >= arr[i]: right[stack.pop()] = iWhat happens: Take a subarray in which two equal values are both the minimum. If both sides stop only at a strictly smaller value, each of the two claims that subarray. It is then counted twice. The blueprint stops at a smaller or equal value on the right, through the
>=in the pop. So only one of the equal values claims it.Example: arr = [1, 1]Mistake: returns 4Fix: returns 3
- You want one best rectangle (height times width), as in Largest Rectangle in Histogram (LC 84), not a total over every subarray. See Histogram Stack
Deep Dive
From listing subarrays to counting shares
Sum of Subarray Minimums (LC 907) asks for the sum of the minimum of every subarray, modulo 10**9 + 7. An array of length N has N * (N + 1) / 2 subarrays, so listing them is too slow for large N.
Count by element instead. For each arr[i], count the subarrays whose minimum it is. That minimum value is added once for each of them, so its share is arr[i] times that count.
arr[i] stays the minimum until a value that beats it. Let left[i] be the index of the previous strictly smaller value, or -1. Let right[i] be the index of the next smaller or equal value, or n. A subarray starts at one of the i - left[i] indexes after left[i], up to i. It ends at one of the right[i] - i indexes from i before right[i]. So the count is (i - left[i]) * (right[i] - i).
What this card adds to Monotonic Stack (Largest Rectangle in Histogram): the popped item is the minimum of the range between its two walls, and the code multiplies value by left count by right count and does not need an area or a width test.
Example: arr = [3, 1, 2, 4]. The shares are 3 * 1 * 1 = 3, 1 * 2 * 3 = 6, 2 * 1 * 2 = 4 and 4 * 1 * 1 = 4. The sum is 17, which is the answer.
One trace: the scan finds both walls, then each index adds its share
The board replays arr = [3, 1, 2, 1], which has a tie. The bottom row is stack, and each cell holds an index.
The scan visits index 1 (value 1) first with a pop. It pops index 0 and writes right[0] = 1. The stack is then empty, so left[1] = -1.
Index 2 (value 2) pops nothing. The top, index 1, is smaller, so left[2] = 1. Index 3 (value 1) pops index 2 and writes right[2] = 3. Then it pops index 1, which has an equal value, and writes right[1] = 3.
The stack is empty after that, so left[3] = -1. The shares are 3 * 1 * 1 = 3, 1 * 2 * 2 = 4, 2 * 1 * 1 = 2 and 1 * 4 * 1 = 4. The total is 13. The subarray [1, 2, 1] is counted once, by index 3.
The trap: strict on one side, non-strict on the other
Two equal values can both be the minimum of one subarray. The count must give that subarray to exactly one of them. The rule is: stop at a strictly smaller value on one side, and at a smaller or equal value on the other side.
In the blueprint, while stack and arr[stack[-1]] >= arr[i] pops an equal value. So the right wall is the next smaller or equal value, and the left wall is strictly smaller. The earlier copy gives up the subarrays that reach the later copy.
If both sides stop only at a strictly smaller value, both copies claim the same subarrays. For arr = [1, 1] the correct answer is 3, because the minimums are 1, 1 and 1. Counting both sides as strict gives 4.
Either side may be the strict one. The sides must be opposite.
Defaults, the modulus, and the cost
Start with right = [n] * n. right[i] is the first index where arr[i] stops being the minimum. If no smaller or equal value follows, the minimum holds up to index n - 1, so the wall is n. With n - 1, those values lose the subarrays that end at the last index. For [3, 1, 2, 4] the result is 9 and not 17.
Take the modulus once, at the end: % MOD. Python integers do not overflow. In Java or C++ a product such as arr[i] * a * b can pass the 32-bit limit, so compute it in 64 bits.
The time is O(N), because every index is pushed once and popped at most once, and the final sum is one pass. The space is O(N) for left, right and stack.
For the sum of maximums, flip the comparison. Sum of Subarray Ranges (LC 2104) is the sum of maximums minus the sum of minimums, so it needs this scan twice.
60-Second Pitch
"Listing all subarrays is O(N^2), so I count by element. For each value I count how many subarrays have it as their minimum. That count is the number of start positions times the number of end positions. The start positions run back to the previous strictly smaller value. The end positions run forward to the next smaller or equal value. One increasing stack finds both walls in a single pass. To avoid counting ties twice, I use a strict comparison on the left and a non-strict comparison on the right. I add value times left count times right count for every index, modulo 10**9 + 7. The time is O(N) and the space is O(N)."
Common Questions
- Why does counting by element work?
Every subarray has exactly one minimum value, and the tie rule gives it to exactly one index. So every subarray is counted once. The sum of the shares of all indexes is the sum of the minimums of all subarrays.
- How do you avoid counting equal values twice?
Make one side strict and the other side non-strict. The code pops with
>=, so the right wall is the next smaller or equal value. The left wall is the previous strictly smaller value. Then a subarray with two equal minimums belongs only to the later copy.- What are the time and space complexity?
O(N)time. Every index is pushed once and popped at most once, and the final sum is one pass.O(N)space forleft,rightandstack.- How would you compute the sum of subarray maximums?
Flip the comparison: pop while
arr[stack[-1]] <= arr[i]. The rest stays the same. Sum of Subarray Ranges (LC 2104) subtracts the sum of minimums from the sum of maximums.
SWE Reasoning
Spot it
- The answer is a sum or a count over all subarrays of their minimum or maximum.
Nis large, so an O(N^2) loop over all subarrays is too slow.- The result is asked modulo a large number such as
10**9 + 7. - Each element's effect depends only on how far it stays the minimum to the left and to the right.
- The array can contain equal values, so the tie rule matters.
The invariant, step by step
- Each subarray has one minimum value. Give each subarray to exactly one index that holds it.
- For index
i,left[i]is the previous strictly smaller value, andright[i]is the next smaller or equal value. - A subarray belongs to
iwhen it starts afterleft[i], ends beforeright[i], and containsi. There are(i - left[i]) * (right[i] - i)of them. - One scan with a stack finds both walls. The values at the indexes in
stackstrictly increase from bottom to top. - When
arr[i]pops an index,iis that index's right wall. After the pops, the top ofstackis the left wall ofi. - Add
arr[i] * (i - left[i]) * (right[i] - i)for every index, then take the result moduloMOD.
Traps
- Strict on both sides. Subarrays with equal minimums are counted twice. Use
>=in the pop and a strict left wall. right = [n - 1] * n. Subarrays that end at the last index are lost. Usen.- No
% MOD. The result is too large. Take the modulus at the end. - Overflow in other languages. Compute the product in 64 bits.
- Looking for the subarray itself. Never build subarrays. Count by element.
Practice
Builds on Histogram Stack, which you haven’t finished yet.
Contribution Technique (Sum over All Subarrays via Each Element's Share)
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.
Contribution Technique
all subarrays ➔ element i is the minimum of (i - left) × (right - i) of them ➔ sum of sharesO(n^2).| 1 | def sum_subarray_mins(arr: list[int]) -> int: |
| 2 | """Sum of Subarray Minimums: add up each element's share as the minimum. |
| 3 | Time: O(N) | Space: O(N) |
| 4 | """ |
| 5 | MOD = 10**9 + 7 |
| 6 | n = len(arr) |
| 7 | left = [-1] * n # Index of the previous strictly smaller element |
| 8 | right = [n] * n # Index of the next smaller-or-equal element |
| 9 | stack: list[int] = [] # Indices with increasing values from bottom to top |
| 10 | |
| 11 | # 1. Visit Every Index Left To Right: |
| 12 | # One pass finds both walls for every index, since each index's walls only depend on values already seen or seen as they arrive. |
| 13 | for i in range(n): |
| 14 | # 2. Resolve Every Index That arr[i] Beats Or Ties: |
| 15 | # While the top of the stack is not strictly smaller than arr[i], arr[i] is the first value to its right that is smaller or equal, so pop it and record i as its right wall. The >= (not >) is what sends a tie's right wall to the later copy. |
| 16 | while stack and arr[stack[-1]] >= arr[i]: |
| 17 | right[stack.pop()] = i # arr[i] is the first value <= the popped one |
| 18 | # 3. Record The Left Wall And Push i: |
| 19 | # After the pops above, whatever remains on top is strictly smaller than arr[i], so it is arr[i]'s left wall; i then joins the stack to serve as a future right wall. |
| 20 | left[i] = stack[-1] if stack else -1 # Top is strictly smaller |
| 21 | stack.append(i) |
| 22 | |
| 23 | # 4. Add Up Every Index's Share: |
| 24 | # arr[i] is the minimum of (i - left[i]) * (right[i] - i) subarrays, so multiplying and summing counts every subarray's minimum exactly once. |
| 25 | return sum(arr[i] * (i - left[i]) * (right[i] - i) for i in range(n)) % MOD |
stack strictly increase from bottom to top, so the index under i is its previous strictly smaller element and the index that pops i is its next smaller-or-equal one.Instead of listing every subarray, ask how many subarrays have arr[i] as their minimum: it stays the minimum until the first smaller value on each side, at left[i] and right[i]. That gives (i - left[i]) * (right[i] - i) subarrays, and one increasing stack finds both boundaries as values are popped. For equal values, stop at a strictly smaller value on one side and a smaller-or-equal value on the other (the >= in the pop), or subarrays with ties are counted twice.
See it run
Contribution Technique, step by step
stack []left [-1, -1, -1, -1]right [4, 4, 4, 4]
The top row is arr. The column number is the index. The bottom row is the stack: the left cell is the bottom, each cell holds an index, and a blank cell is an unused slot. A wall of -1, or a wall equal to the length of arr, has no cell, because it is outside arr.
ithe index being read nowpoppedthe index taken off the stack, whose right wall is written nowleft wallthe index in left[i], a strictly smaller value on the leftright wallthe index in right[i], a smaller or equal value on the rightpushedthe index that was just pushed
Start: stack is empty, every left is -1 and every right is 4.
Gotcha 1 of 3
- The trap
Gotcha 1: Stopping at a strictly smaller value on both sides
Mistakefor i in range(n - 1, -1, -1): while stack and arr[stack[-1]] >= arr[i]: stack.pop() right[i] = stack[-1] if stack else nFixwhile stack and arr[stack[-1]] >= arr[i]: right[stack.pop()] = iWhat happens: Take a subarray in which two equal values are both the minimum. If both sides stop only at a strictly smaller value, each of the two claims that subarray. It is then counted twice. The blueprint stops at a smaller or equal value on the right, through the
>=in the pop. So only one of the equal values claims it.Example: arr = [1, 1]Mistake: returns 4Fix: returns 3
- You want one best rectangle (height times width), as in Largest Rectangle in Histogram (LC 84), not a total over every subarray. See Histogram Stack
Deep Dive
From listing subarrays to counting shares
Sum of Subarray Minimums (LC 907) asks for the sum of the minimum of every subarray, modulo 10**9 + 7. An array of length N has N * (N + 1) / 2 subarrays, so listing them is too slow for large N.
Count by element instead. For each arr[i], count the subarrays whose minimum it is. That minimum value is added once for each of them, so its share is arr[i] times that count.
arr[i] stays the minimum until a value that beats it. Let left[i] be the index of the previous strictly smaller value, or -1. Let right[i] be the index of the next smaller or equal value, or n. A subarray starts at one of the i - left[i] indexes after left[i], up to i. It ends at one of the right[i] - i indexes from i before right[i]. So the count is (i - left[i]) * (right[i] - i).
What this card adds to Monotonic Stack (Largest Rectangle in Histogram): the popped item is the minimum of the range between its two walls, and the code multiplies value by left count by right count and does not need an area or a width test.
Example: arr = [3, 1, 2, 4]. The shares are 3 * 1 * 1 = 3, 1 * 2 * 3 = 6, 2 * 1 * 2 = 4 and 4 * 1 * 1 = 4. The sum is 17, which is the answer.
One trace: the scan finds both walls, then each index adds its share
The board replays arr = [3, 1, 2, 1], which has a tie. The bottom row is stack, and each cell holds an index.
The scan visits index 1 (value 1) first with a pop. It pops index 0 and writes right[0] = 1. The stack is then empty, so left[1] = -1.
Index 2 (value 2) pops nothing. The top, index 1, is smaller, so left[2] = 1. Index 3 (value 1) pops index 2 and writes right[2] = 3. Then it pops index 1, which has an equal value, and writes right[1] = 3.
The stack is empty after that, so left[3] = -1. The shares are 3 * 1 * 1 = 3, 1 * 2 * 2 = 4, 2 * 1 * 1 = 2 and 1 * 4 * 1 = 4. The total is 13. The subarray [1, 2, 1] is counted once, by index 3.
The trap: strict on one side, non-strict on the other
Two equal values can both be the minimum of one subarray. The count must give that subarray to exactly one of them. The rule is: stop at a strictly smaller value on one side, and at a smaller or equal value on the other side.
In the blueprint, while stack and arr[stack[-1]] >= arr[i] pops an equal value. So the right wall is the next smaller or equal value, and the left wall is strictly smaller. The earlier copy gives up the subarrays that reach the later copy.
If both sides stop only at a strictly smaller value, both copies claim the same subarrays. For arr = [1, 1] the correct answer is 3, because the minimums are 1, 1 and 1. Counting both sides as strict gives 4.
Either side may be the strict one. The sides must be opposite.
Defaults, the modulus, and the cost
Start with right = [n] * n. right[i] is the first index where arr[i] stops being the minimum. If no smaller or equal value follows, the minimum holds up to index n - 1, so the wall is n. With n - 1, those values lose the subarrays that end at the last index. For [3, 1, 2, 4] the result is 9 and not 17.
Take the modulus once, at the end: % MOD. Python integers do not overflow. In Java or C++ a product such as arr[i] * a * b can pass the 32-bit limit, so compute it in 64 bits.
The time is O(N), because every index is pushed once and popped at most once, and the final sum is one pass. The space is O(N) for left, right and stack.
For the sum of maximums, flip the comparison. Sum of Subarray Ranges (LC 2104) is the sum of maximums minus the sum of minimums, so it needs this scan twice.
60-Second Pitch
"Listing all subarrays is O(N^2), so I count by element. For each value I count how many subarrays have it as their minimum. That count is the number of start positions times the number of end positions. The start positions run back to the previous strictly smaller value. The end positions run forward to the next smaller or equal value. One increasing stack finds both walls in a single pass. To avoid counting ties twice, I use a strict comparison on the left and a non-strict comparison on the right. I add value times left count times right count for every index, modulo 10**9 + 7. The time is O(N) and the space is O(N)."
Common Questions
- Why does counting by element work?
Every subarray has exactly one minimum value, and the tie rule gives it to exactly one index. So every subarray is counted once. The sum of the shares of all indexes is the sum of the minimums of all subarrays.
- How do you avoid counting equal values twice?
Make one side strict and the other side non-strict. The code pops with
>=, so the right wall is the next smaller or equal value. The left wall is the previous strictly smaller value. Then a subarray with two equal minimums belongs only to the later copy.- What are the time and space complexity?
O(N)time. Every index is pushed once and popped at most once, and the final sum is one pass.O(N)space forleft,rightandstack.- How would you compute the sum of subarray maximums?
Flip the comparison: pop while
arr[stack[-1]] <= arr[i]. The rest stays the same. Sum of Subarray Ranges (LC 2104) subtracts the sum of minimums from the sum of maximums.
SWE Reasoning
Spot it
- The answer is a sum or a count over all subarrays of their minimum or maximum.
Nis large, so an O(N^2) loop over all subarrays is too slow.- The result is asked modulo a large number such as
10**9 + 7. - Each element's effect depends only on how far it stays the minimum to the left and to the right.
- The array can contain equal values, so the tie rule matters.
The invariant, step by step
- Each subarray has one minimum value. Give each subarray to exactly one index that holds it.
- For index
i,left[i]is the previous strictly smaller value, andright[i]is the next smaller or equal value. - A subarray belongs to
iwhen it starts afterleft[i], ends beforeright[i], and containsi. There are(i - left[i]) * (right[i] - i)of them. - One scan with a stack finds both walls. The values at the indexes in
stackstrictly increase from bottom to top. - When
arr[i]pops an index,iis that index's right wall. After the pops, the top ofstackis the left wall ofi. - Add
arr[i] * (i - left[i]) * (right[i] - i)for every index, then take the result moduloMOD.
Traps
- Strict on both sides. Subarrays with equal minimums are counted twice. Use
>=in the pop and a strict left wall. right = [n - 1] * n. Subarrays that end at the last index are lost. Usen.- No
% MOD. The result is too large. Take the modulus at the end. - Overflow in other languages. Compute the product in 64 bits.
- Looking for the subarray itself. Never build subarrays. Count by element.