You're solving "Sum of Subarray Minimums" (LeetCode #907). The brute force is obvious: generate all subarrays, find the minimum of each, sum them up. O(n³) or O(n²) at best.
But there's an elegant O(n) solution using a technique that feels like magic: the contribution technique with monotonic stacks.
The insight: Instead of asking "what's the minimum of each subarray?", ask "for how many subarrays is element X the minimum?" Then multiply by X and sum all contributions.
This guide will teach you the complete contribution technique, how to find boundaries with monotonic stacks, handling duplicates correctly, and solving advanced counting/summing problems.
Contribution Technique:
element_value × count_of_subarraysHow to find count:
(i - left_boundary) × (right_boundary - i)Time: O(n), Space: O(n)
Critical detail: Handle duplicates with strict inequality on one side, non-strict on the other
Given an array, find the sum of minimums of all subarrays.
Example:
Input: arr = [3, 1, 2, 4]
Output: 17
Explanation:
Subarrays and their minimums:
[3] → min = 3
[3,1] → min = 1
[3,1,2] → min = 1
[3,1,2,4] → min = 1
[1] → min = 1
[1,2] → min = 1
[1,2,4] → min = 1
[2] → min = 2
[2,4] → min = 2
[4] → min = 4
Sum = 3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17def sumSubarrayMins_brute(arr):
"""
Generate all subarrays, find min of each.
Time: O(n²)
Space: O(1)
"""
total = 0
n = len(arr)
for i in range(n):
min_val = arr[i]
for j in range(i, n):
min_val = min(min_val, arr[j])
total += min_val
return total % (10**9 + 7)Time complexity: O(n²) - for each starting position, scan to the end
Problem: TLE (Time Limit Exceeded) for large inputs
Instead of: "For each subarray, what's the minimum?"
Ask: "For each element, in how many subarrays is it the minimum?"
Visual example:
Array: [3, 1, 2, 4]
[0 1 2 3]
Element 1 (index 1):
- Subarrays where 1 is minimum:
[1] ✓
[3,1] ✓
[1,2] ✓
[3,1,2] ✓
[1,2,4] ✓
[3,1,2,4] ✓
Count: 6 subarrays
Contribution: 1 × 6 = 6Formula:
Total sum = Σ (arr[i] × count_of_subarrays_where_arr[i]_is_min)For element at index i to be the minimum of a subarray:
iThis means:
Boundaries:
left[i] = index of next smaller element to the left (or -1)right[i] = index of next smaller element to the right (or n)Count formula:
left_count = i - left[i] # Number of positions to the left
right_count = right[i] - i # Number of positions to the right
count = left_count × right_countVisual:
Array: [3, 1, 2, 4]
[0 1 2 3]
For element 1 at index 1:
- Next smaller to left: none (left[1] = -1)
- Next smaller to right: none (right[1] = 4)
left_count = 1 - (-1) = 2 (can start at index 0 or 1)
right_count = 4 - 1 = 3 (can end at index 1, 2, or 3)
count = 2 × 3 = 6 ✓def find_next_smaller_right(arr):
"""
For each element, find index of next smaller element to the right.
Time: O(n)
Space: O(n)
"""
n = len(arr)
right = [n] * n # Default: no smaller element (boundary at n)
stack = [] # Monotonic increasing stack
for i in range(n):
# Pop all elements >= current (current is smaller)
while stack and arr[i] < arr[stack[-1]]:
idx = stack.pop()
right[idx] = i # arr[i] is next smaller for arr[idx]
stack.append(i)
# Elements remaining in stack have no next smaller
# (already initialized to n)
return right
# Example
arr = [3, 1, 2, 4]
print(find_next_smaller_right(arr))
# Output: [1, 4, 4, 4]
# Explanation:
# - arr[0]=3: next smaller is arr[1]=1
# - arr[1]=1: no smaller to right
# - arr[2]=2: no smaller to right
# - arr[3]=4: no smaller to rightdef find_next_smaller_left(arr):
"""
For each element, find index of next smaller element to the left.
Time: O(n)
Space: O(n)
"""
n = len(arr)
left = [-1] * n # Default: no smaller element (boundary at -1)
stack = [] # Monotonic increasing stack
# Iterate right to left
for i in range(n - 1, -1, -1):
# Pop all elements >= current
while stack and arr[i] < arr[stack[-1]]:
idx = stack.pop()
left[idx] = i # arr[i] is next smaller for arr[idx]
stack.append(i)
return left
# Example
arr = [3, 1, 2, 4]
print(find_next_smaller_left(arr))
# Output: [-1, -1, 1, 2]
# Explanation:
# - arr[0]=3: no smaller to left
# - arr[1]=1: no smaller to left
# - arr[2]=2: next smaller is arr[1]=1
# - arr[3]=4: next smaller is arr[2]=2def sumSubarrayMins(arr):
"""
LeetCode #907: Sum of Subarray Minimums
Approach: Contribution technique with monotonic stack
1. For each element, find next smaller on both sides
2. Calculate count of subarrays where it's minimum
3. Sum all contributions
Time: O(n)
Space: O(n)
"""
n = len(arr)
MOD = 10**9 + 7
# Find boundaries
left = [-1] * n # Next smaller to left
right = [n] * n # Next smaller to right
# Find next smaller to right
stack = []
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Find next smaller to left
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] < arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
# Calculate contribution of each element
result = 0
for i in range(n):
left_count = i - left[i] # Positions to the left
right_count = right[i] - i # Positions to the right
count = left_count * right_count
contribution = arr[i] * count
result = (result + contribution) % MOD
return result
# Example
print(sumSubarrayMins([3, 1, 2, 4]))
# Output: 17Array: [3, 1, 2, 4]
[0 1 2 3]
Step 1: Find next smaller to right
i=0, val=3: stack=[], push 0, stack=[0]
i=1, val=1: 1 < arr[0]=3, right[0]=1, stack=[], push 1, stack=[1]
i=2, val=2: 2 > 1, push 2, stack=[1,2]
i=3, val=4: 4 > 2, push 3, stack=[1,2,3]
right = [1, 4, 4, 4]
Step 2: Find next smaller to left
i=3, val=4: stack=[], push 3, stack=[3]
i=2, val=2: 2 < arr[3]=4, left[3]=2, stack=[], push 2, stack=[2]
i=1, val=1: 1 < arr[2]=2, left[2]=1, stack=[], push 1, stack=[1]
i=0, val=3: 3 > 1, push 0, stack=[1,0]
left = [-1, -1, 1, 2]
Step 3: Calculate contributions
i=0, arr[0]=3:
left_count = 0 - (-1) = 1
right_count = 1 - 0 = 1
count = 1 × 1 = 1
contribution = 3 × 1 = 3
i=1, arr[1]=1:
left_count = 1 - (-1) = 2
right_count = 4 - 1 = 3
count = 2 × 3 = 6
contribution = 1 × 6 = 6
i=2, arr[2]=2:
left_count = 2 - 1 = 1
right_count = 4 - 2 = 2
count = 1 × 2 = 2
contribution = 2 × 2 = 4
i=3, arr[3]=4:
left_count = 3 - 2 = 1
right_count = 4 - 3 = 1
count = 1 × 1 = 1
contribution = 4 × 1 = 4
Total = 3 + 6 + 4 + 4 = 17 ✓Array: [2, 2, 2]
If we use strict < on both sides:
# Both use <
while stack and arr[i] < arr[stack[-1]]: # Right
while stack and arr[i] < arr[stack[-1]]: # LeftProblem: Each 2 thinks it's the minimum of subarray [2, 2], counting it twice!
Use strict inequality on ONE side, non-strict on the OTHER:
# Correct approach
# Right: strict <
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
# Left: non-strict <=
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = iWhy this works:
Visual:
Array: [2, 2, 2]
[0 1 2]
With asymmetric comparison:
i=0: left=[-1], right=[1] (claims [2])
i=1: left=[0], right=[2] (claims [2,2])
i=2: left=[1], right=[3] (claims [2,2,2])
Each subarray counted exactly once ✓def sumSubarrayMins(arr):
"""
Correct handling of duplicates.
Time: O(n)
Space: O(n)
"""
n = len(arr)
MOD = 10**9 + 7
left = [-1] * n
right = [n] * n
# Right: strict < (pop when current is strictly smaller)
stack = []
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Left: non-strict <= (pop when current is smaller or equal)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
# Calculate contributions
result = 0
for i in range(n):
count = (i - left[i]) * (right[i] - i)
result = (result + arr[i] * count) % MOD
return resultSee detailed guide: Handling Duplicates
Find the sum of (max - min) for all subarrays.
def subArrayRanges(nums):
"""
LeetCode #2104: Sum of Subarray Ranges
Approach:
- Sum of (max - min) = Sum of max - Sum of min
- Use contribution technique twice
Time: O(n)
Space: O(n)
"""
def sum_of_mins(arr):
n = len(arr)
left, right = [-1] * n, [n] * n
stack = []
# Next smaller to right (strict <)
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Next smaller to left (non-strict <=)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
total = 0
for i in range(n):
count = (i - left[i]) * (right[i] - i)
total += arr[i] * count
return total
def sum_of_maxs(arr):
n = len(arr)
left, right = [-1] * n, [n] * n
stack = []
# Next greater to right (strict >)
for i in range(n):
while stack and arr[i] > arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Next greater to left (non-strict >=)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] >= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
total = 0
for i in range(n):
count = (i - left[i]) * (right[i] - i)
total += arr[i] * count
return total
return sum_of_maxs(nums) - sum_of_mins(nums)
# Example
print(subArrayRanges([1, 2, 3]))
# Output: 4
# Explanation:
# [1]: max-min = 0
# [2]: max-min = 0
# [3]: max-min = 0
# [1,2]: max-min = 1
# [2,3]: max-min = 1
# [1,2,3]: max-min = 2
# Sum = 0+0+0+1+1+2 = 4def count_subarrays_with_min(arr, target):
"""
Count subarrays where target element is the minimum.
Time: O(n)
Space: O(n)
"""
n = len(arr)
# Find index of target
target_idx = arr.index(target)
# Find boundaries
left = [-1] * n
right = [n] * n
stack = []
# Next smaller to right
for i in range(n):
while stack and arr[i] < arr[stack[-1]]:
right[stack.pop()] = i
stack.append(i)
# Next smaller to left
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[i] <= arr[stack[-1]]:
left[stack.pop()] = i
stack.append(i)
# Count for target element
i = target_idx
left_count = i - left[i]
right_count = right[i] - i
count = left_count * right_count
return count❌ Wrong:
# Both use <
while stack and arr[i] < arr[stack[-1]]: # Right
while stack and arr[i] < arr[stack[-1]]: # Left
# Duplicates counted multiple times!✅ Correct:
# Right: strict <
while stack and arr[i] < arr[stack[-1]]:
# Left: non-strict <=
while stack and arr[i] <= arr[stack[-1]]:❌ Wrong:
count = (i - left[i] - 1) * (right[i] - i - 1) # Off by one!✅ Correct:
count = (i - left[i]) * (right[i] - i) # Correct❌ Wrong:
result += arr[i] * count # Can overflow!✅ Correct:
result = (result + arr[i] * count) % MOD❌ Wrong:
left = [0] * n # Wrong default!
right = [0] * n✅ Correct:
left = [-1] * n # Correct: boundary at -1
right = [n] * n # Correct: boundary at nOperations:
Total: O(n) + O(n) + O(n) = O(n)
Space used:
left array: O(n)right array: O(n)Total: O(n)
Master the contribution technique:
The contribution technique transforms O(n²) counting/summing problems into O(n) solutions using monotonic stacks.
Key principles:
(i - left[i]) × (right[i] - i)The formula:
Total = Σ (arr[i] × count_of_subarrays_where_arr[i]_is_min)Critical detail: Asymmetric comparison prevents double-counting duplicates.
Master this technique, and you'll solve an entire class of advanced problems with elegance.
Next steps:
Next time you see "sum of minimums" or "count subarrays," reach for the contribution technique.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free