127. Sum of Subarray Minimums
🔗 LeetCode Problem: 907. Sum of Subarray Minimums
📊 Difficulty: Medium
🏷️ Topics: Array, Stack, Monotonic Stack, Dynamic Programming
Problem Statement
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.
Example 1:
Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]
Minimums are: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1
Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17
Example 2:
Input: arr = [11,81,94,43,3]
Output: 444
Constraints:
- 1 <= arr.length <= 3 * 10^4
- 1 <= arr[i] <= 3 * 10^4
🌟 Understanding the Problem
What Are We Really Calculating?
For array [3, 1, 2, 4]:
All subarrays:
Length 1: [3] → min = 3
[1] → min = 1
[2] → min = 2
[4] → min = 4
Length 2: [3,1] → min = 1
[1,2] → min = 1
[2,4] → min = 2
Length 3: [3,1,2] → min = 1
[1,2,4] → min = 1
Length 4: [3,1,2,4] → min = 1
Sum = 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17
Key observation: We need the minimum of EVERY possible subarray!
How Many Subarrays Are There?
For array of length n:
- Length 1 subarrays: n
- Length 2 subarrays: n-1
- Length 3 subarrays: n-2
- ...
- Length n subarrays: 1
Total = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
For n=4: 4*5/2 = 10 subarrays ✓
💡 Connection to Previous Problems
This Is Different From What We've Seen!
┌─────────────────────────────────────────────────────────┐
│ Previous Problems │ Sum of Subarray Minimums │
├─────────────────────────────────────────────────────────┤
│ Find ONE element: │ Find ALL minimums: │
│ - Next greater │ - Every subarray │
│ - Previous greater │ - Count contributions │
│ │ │
│ Return: Element/Distance │ Return: SUM of all mins │
│ │ │
│ Pattern: Per element │ Pattern: Per element BUT │
│ query │ contribution │
└─────────────────────────────────────────────────────────┘
New twist:
Instead of "find something for each element"
We need: "how much does each element CONTRIBUTE to the total?"
💡 How to DISCOVER the Solution
Let me show you the natural thought progression.
🎯 STEP 1: The Obvious Approach
First thought:
"Generate all subarrays, find minimum of each, sum them up!"
for i in 0 to n-1:
for j in i to n-1:
subarray = arr[i..j]
min_val = min(subarray)
total += min_val
Let's code this:
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long total = 0;
int MOD = 1_000_000_007;
// For each starting position
for (int i = 0; i < n; i++) {
int min = arr[i];
// For each ending position
for (int j = i; j < n; j++) {
min = Math.min(min, arr[j]); // Update minimum
total = (total + min) % MOD;
}
}
return (int) total;
}
Does it work?
Yes! ✓
arr = [3, 1, 2, 4]
i=0: subarrays starting at 0
[3]: min=3, total=3
[3,1]: min=1, total=4
[3,1,2]: min=1, total=5
[3,1,2,4]: min=1, total=6
i=1: subarrays starting at 1
[1]: min=1, total=7
[1,2]: min=1, total=8
[1,2,4]: min=1, total=9
i=2: subarrays starting at 2
[2]: min=2, total=11
[2,4]: min=2, total=13
i=3: subarrays starting at 3
[4]: min=4, total=17 ✓
Time complexity?
Outer loop: n iterations
Inner loop: up to n iterations
O(n²) ❌
For n = 30,000 (constraint):
30,000² = 900,000,000 operations
Too slow!
🎯 STEP 2: Can We Avoid Generating All Subarrays?
Key question:
Do we really need to look at EVERY subarray individually?
Think about it differently:
Instead of: "For each subarray, what's the minimum?"
Ask: "For each ELEMENT, in how many subarrays is it the minimum?"
This is a HUGE insight!
Example:
arr = [3, 1, 2, 4]
↑
Consider element 1 at index 1:
In which subarrays is 1 the minimum?
[1] → 1 is min ✓
[3,1] → 1 is min ✓
[1,2] → 1 is min ✓
[3,1,2] → 1 is min ✓
[1,2,4] → 1 is min ✓
[3,1,2,4] → 1 is min ✓
Element 1 is the minimum in 6 subarrays!
Contribution: 1 × 6 = 6
The new approach:
For each element arr[i]:
1. Count how many subarrays have arr[i] as minimum
2. Contribution = arr[i] × count
3. Total = sum of all contributions
🎯 STEP 3: Counting Subarrays Where Element is Minimum
How do we count?
For element at index i to be minimum in a subarray:
- Subarray must INCLUDE index i
- All elements in subarray must be >= arr[i]
Think about boundaries:
arr = [3, 1, 2, 4]
↑
index 1 (value 1)
Look LEFT from index 1:
- Index 0 has value 3 (3 > 1, ok!)
- Can extend to index 0
Look RIGHT from index 1:
- Index 2 has value 2 (2 > 1, ok!)
- Index 3 has value 4 (4 > 1, ok!)
- Can extend to index 3
So subarrays with 1 as minimum:
Can start at: 0 or 1 (2 choices)
Can end at: 1, 2, or 3 (3 choices)
Total: 2 × 3 = 6 subarrays ✓
The pattern:
For element at index i:
- Find how far LEFT we can go (while elements >= arr[i])
- Find how far RIGHT we can go (while elements >= arr[i])
left_count = number of positions to the left (including i)
right_count = number of positions to the right (including i)
Total subarrays = left_count × right_count
🎯 STEP 4: First Attempt - Count in Both Directions
Algorithm:
For each element arr[i]:
1. Scan left: count consecutive elements >= arr[i]
2. Scan right: count consecutive elements >= arr[i]
3. Multiply counts
4. Add arr[i] × count to total
Let's code it:
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long total = 0;
int MOD = 1_000_000_007;
for (int i = 0; i < n; i++) {
// Count elements to the left >= arr[i]
int left = 0;
for (int j = i; j >= 0 && arr[j] >= arr[i]; j--) {
left++;
}
// Count elements to the right >= arr[i]
int right = 0;
for (int j = i; j < n && arr[j] >= arr[i]; j++) {
right++;
}
// Contribution of arr[i]
long contribution = (long) arr[i] * left * right;
total = (total + contribution) % MOD;
}
return (int) total;
}
Does it work?
Let's trace: arr = [3, 1, 2, 4]
i=0 (value 3):
left: 3 >= 3? YES, count=1, stop (boundary)
right: 3 >= 3? YES, count=1, then 1 >= 3? NO, stop
contribution = 3 × 1 × 1 = 3
i=1 (value 1):
left: 1 >= 1? YES, count=1, then 3 >= 1? YES, count=2, stop
right: 1 >= 1? YES, count=1, then 2 >= 1? YES, count=2,
then 4 >= 1? YES, count=3, stop
contribution = 1 × 2 × 3 = 6
i=2 (value 2):
left: 2 >= 2? YES, count=1, then 1 >= 2? NO, stop
right: 2 >= 2? YES, count=1, then 4 >= 2? YES, count=2, stop
contribution = 2 × 1 × 2 = 4
i=3 (value 4):
left: 4 >= 4? YES, count=1, then 2 >= 4? NO, stop
right: 4 >= 4? YES, count=1, stop (boundary)
contribution = 4 × 1 × 1 = 4
Total = 3 + 6 + 4 + 4 = 17 ✓
Time complexity?
For each element: O(n)
- Scan left: up to n
- Scan right: up to n
Total: O(n²) ❌
Still too slow!
🎯 STEP 5: The Bottleneck
What's taking time?
For EACH element, we scan left and right.
But notice:
We're asking the same question repeatedly!
"How far can I extend while elements are >= current?"
This is similar to finding boundaries...
Like finding "previous smaller" and "next smaller"!
Wait! This sounds familiar!
From Daily Temperatures / Stock Span:
We used monotonic stack to find next greater!
Here we need:
Previous smaller element (left boundary)
Next smaller element (right boundary)
🎯 STEP 6: Using Monotonic Stack for Boundaries
The insight:
For each element arr[i]:
- Left boundary = index of previous SMALLER element
- Right boundary = index of next SMALLER element
left_count = i - left_boundary
right_count = right_boundary - i
Total subarrays = left_count × right_count
Example:
arr = [3, 1, 2, 4]
↑
index 1 (value 1)
Previous smaller than 1:
- Look left: 3? NO (3 > 1)
- No previous smaller
- left_boundary = -1 (before array start)
Next smaller than 1:
- Look right: 2? NO (2 > 1), 4? NO (4 > 1)
- No next smaller
- right_boundary = 4 (after array end)
left_count = 1 - (-1) = 2
right_count = 4 - 1 = 3
Total = 2 × 3 = 6 ✓
How to find these boundaries efficiently?
Monotonic stack!
For previous smaller:
- Scan left to right
- Maintain increasing stack
- When we see element, stack top is previous smaller
For next smaller:
- Scan left to right
- Maintain increasing stack
- When element pops others, it's their next smaller
🎯 STEP 7: Building the Stack Solution
Two passes needed:
Pass 1: Find previous smaller element (left boundaries)
Scan left to right with increasing stack:
for i in 0 to n-1:
while stack not empty AND arr[stack.top] >= arr[i]:
pop // These are NOT smaller, remove them
if stack empty:
left[i] = -1 // No previous smaller
else:
left[i] = stack.top // Previous smaller
push i
Pass 2: Find next smaller element (right boundaries)
Scan left to right with increasing stack:
for i in 0 to n-1:
while stack not empty AND arr[stack.top] > arr[i]:
idx = pop
right[idx] = i // i is next smaller for idx
push i
// Elements remaining in stack have no next smaller
while stack not empty:
idx = pop
right[idx] = n // Beyond array
Wait, there's a subtle issue!
🎯 STEP 8: Handling Duplicates
Problem with duplicates:
arr = [2, 2]
For first 2 (index 0):
Subarrays where it's minimum: [2] (itself)
Contribution = 2 × 1 = 2
For second 2 (index 1):
Subarrays where it's minimum: [2] (itself)
Contribution = 2 × 1 = 2
Total should be: 2 + 2 + 2 = 6
[2] at index 0: min = 2
[2] at index 1: min = 2
[2,2]: min = 2
But with our formula:
first 2: left_count = 1, right_count = 2 → 1×2 = 2 subarrays
second 2: left_count = 2, right_count = 1 → 2×1 = 2 subarrays
We're counting [2,2] TWICE! ❌
The fix:
When we have duplicates, we need to be careful about boundaries!
Solution: Use STRICT inequality in one direction:
- Previous smaller: arr[j] >= arr[i] (can be equal)
- Next smaller: arr[j] > arr[i] (strictly greater)
OR vice versa:
- Previous smaller: arr[j] > arr[i] (strictly greater)
- Next smaller: arr[j] >= arr[i] (can be equal)
This ensures each subarray is counted EXACTLY ONCE!
Why this works:
arr = [2, 2]
Using >= for left, > for right:
First 2 (index 0):
Previous smaller (<= comparison): none, boundary = -1
Next smaller (< comparison): none (2 is not < 2), boundary = 2
left_count = 0 - (-1) = 1
right_count = 2 - 0 = 2
Contribution: 2 × 1 × 2 = 4 (counts [2] and [2,2])
Second 2 (index 1):
Previous smaller (<= comparison): 2 at index 0, boundary = 0
Next smaller (< comparison): none, boundary = 2
left_count = 1 - 0 = 1
right_count = 2 - 1 = 1
Contribution: 2 × 1 × 1 = 2 (counts only [2] at index 1)
Total: 4 + 2 = 6 ✓
🎯 STEP 9: Why Monotonic Stack Works Here
Stack maintains increasing elements:
When we scan left to right:
- Stack stores indices in increasing order of VALUES
- When we see smaller element, we pop larger ones
- Stack top is the previous smaller element!
Example trace:
arr = [3, 1, 2, 4]
i=0 (value 3):
Stack: []
Previous smaller: none
Push 0
Stack: [0]
i=1 (value 1):
Stack: [0]
Compare: arr[0]=3 >= 1? YES, pop
Stack: []
Previous smaller: none (-1)
Push 1
Stack: [1]
i=2 (value 2):
Stack: [1]
Compare: arr[1]=1 >= 2? NO
Previous smaller: index 1
Push 2
Stack: [1, 2]
Note: Stack has 1 < 2 (increasing!) ✓
i=3 (value 4):
Stack: [1, 2]
Compare: arr[2]=2 >= 4? NO
Previous smaller: index 2
Push 3
Stack: [1, 2, 3]
Still increasing: 1 < 2 < 4 ✓
For next smaller, similar logic:
When we pop an element, the current element is its next smaller!
🎯 STEP 10: The Complete Algorithm
Three steps:
Step 1: Find left boundaries (previous smaller or equal)
Use stack, scan left to right
Pop when arr[stack.top] >= arr[i]
Step 2: Find right boundaries (next strictly smaller)
Use stack, scan left to right
Pop when arr[stack.top] > arr[i]
Current index i is next smaller for popped element
Step 3: Calculate contribution
For each index i:
left_count = i - left_boundary[i]
right_count = right_boundary[i] - i
contribution = arr[i] × left_count × right_count
total += contribution
Time complexity:
Each pass: O(n)
- Each element pushed once
- Each element popped once
Total: O(n) ✓
🎯 Approach 1: Brute Force (Generate All Subarrays)
Implementation
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long total = 0;
int MOD = 1_000_000_007;
for (int i = 0; i < n; i++) {
int min = arr[i];
for (int j = i; j < n; j++) {
min = Math.min(min, arr[j]);
total = (total + min) % MOD;
}
}
return (int) total;
}
Complexity Analysis
⏰ Time: O(n²)
Outer loop: n iterations
Inner loop: n iterations
Total: n × n = O(n²)
💾 Space: O(1)
🎯 Approach 2: Count Left and Right (Still Brute Force)
Implementation
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long total = 0;
int MOD = 1_000_000_007;
for (int i = 0; i < n; i++) {
int left = 0;
for (int j = i; j >= 0 && arr[j] >= arr[i]; j--) {
left++;
}
int right = 0;
for (int j = i; j < n && arr[j] >= arr[i]; j++) {
right++;
}
long contribution = (long) arr[i] * left * right;
total = (total + contribution) % MOD;
}
return (int) total;
}
Complexity Analysis
⏰ Time: O(n²)
Still scanning left and right for each element
💾 Space: O(1)
🎯 Approach 3: Monotonic Stack (Optimal)
The Strategy
1. Find previous smaller element for each index (left boundary)
2. Find next smaller element for each index (right boundary)
3. Calculate: left_count × right_count for each element
4. Contribution = arr[i] × left_count × right_count
5. Use >= for one direction, > for other (handle duplicates!)
Why Stack? (Complete Reasoning)
Why not scan for each element?
Scanning left and right for EACH element: O(n²)
We're repeating work!
Stack approach:
- Process each element ONCE for left boundaries
- Process each element ONCE for right boundaries
- Total: O(n) ✓
Why monotonic increasing stack?
We want to find SMALLER elements:
- Stack maintains increasing values
- Top of stack = largest so far
- When we see smaller, we pop larger
- What remains is smaller!
Example: Stack [1, 2, 3]
New element: 2
Pop 3 (3 > 2)
Top is now 1 (1 < 2, this is previous smaller!)
Why two passes?
First pass: Previous smaller (scan left to right)
- Stack tells us what came before
Second pass: Next smaller (scan left to right)
- When we pop, current element is next smaller
Can't do both in one pass efficiently!
Implementation
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
int MOD = 1_000_000_007;
// Arrays to store boundaries
int[] left = new int[n]; // Distance to previous smaller
int[] right = new int[n]; // Distance to next smaller
// Stack stores indices
Stack<Integer> stack = new Stack<>();
// Find previous smaller or equal (left boundaries)
for (int i = 0; i < n; i++) {
// Pop elements >= current (not strictly smaller)
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
stack.pop();
}
// Distance from previous smaller
left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
// Clear stack for next pass
stack.clear();
// Find next strictly smaller (right boundaries)
for (int i = 0; i < n; i++) {
// Pop elements > current (strictly greater)
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int idx = stack.pop();
right[idx] = i - idx;
}
stack.push(i);
}
// Remaining elements have no next smaller
while (!stack.isEmpty()) {
int idx = stack.pop();
right[idx] = n - idx;
}
// Calculate total
long total = 0;
for (int i = 0; i < n; i++) {
long contribution = (long) arr[i] * left[i] * right[i];
total = (total + contribution) % MOD;
}
return (int) total;
}
Line-by-Line Explanation
int[] left = new int[n];
int[] right = new int[n];
// WHY arrays? Store distance to boundaries for each element
// left[i] = how many elements to left (including i)
// right[i] = how many elements to right (including i)
// First pass: Previous smaller or equal
for (int i = 0; i < n; i++) {
// WHY left to right? Building up as we go
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
// WHY >= ? Allow equal values on the left
// This prevents double counting duplicates
stack.pop();
}
left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
// WHY i + 1 if empty? All elements from 0 to i work
// WHY i - stack.peek()? Distance to previous smaller
stack.push(i);
// Store current for future elements
}
// Second pass: Next strictly smaller
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
// WHY > (strict)? Combined with >= above prevents double count
// If equal, left side claims it, right side doesn't
int idx = stack.pop();
right[idx] = i - idx;
// Current i is next smaller for idx!
}
stack.push(i);
}
// Handle remaining
while (!stack.isEmpty()) {
int idx = stack.pop();
right[idx] = n - idx;
// No next smaller, goes to end
}
// Calculate contribution
for (int i = 0; i < n; i++) {
long contribution = (long) arr[i] * left[i] * right[i];
// arr[i] is minimum in left[i] × right[i] subarrays
total = (total + contribution) % MOD;
}
Detailed Dry Run
Input: arr = [3, 1, 2, 4]
═══════════════════════════════════════════════════════════
Pass 1: Find Previous Smaller or Equal (left boundaries)
═══════════════════════════════════════════════════════════
i=0, arr[0]=3
Stack: []
While: empty, skip
left[0] = 0 + 1 = 1
WHY? No previous smaller, can extend to start
Push 0
Stack: [0]
i=1, arr[1]=1
Stack: [0]
While: arr[0]=3 >= 1? YES
Pop 0
WHY? 3 is not smaller than 1
Stack: []
left[1] = 1 + 1 = 2
WHY? No previous smaller, extends from index 0
Push 1
Stack: [1]
i=2, arr[2]=2
Stack: [1]
While: arr[1]=1 >= 2? NO
WHY? 1 < 2, it IS smaller, keep it
Stack: [1]
left[2] = 2 - 1 = 1
WHY? Previous smaller at index 1, distance = 1
Push 2
Stack: [1, 2]
i=3, arr[3]=4
Stack: [1, 2]
While: arr[2]=2 >= 4? NO
Stack: [1, 2]
left[3] = 3 - 2 = 1
WHY? Previous smaller at index 2, distance = 1
Push 3
Stack: [1, 2, 3]
Result: left = [1, 2, 1, 1]
═══════════════════════════════════════════════════════════
Pass 2: Find Next Strictly Smaller (right boundaries)
═══════════════════════════════════════════════════════════
Clear stack
Stack: []
i=0, arr[0]=3
Stack: []
While: empty, skip
Push 0
Stack: [0]
i=1, arr[1]=1
Stack: [0]
While: arr[0]=3 > 1? YES ← Strict comparison!
Pop 0
right[0] = 1 - 0 = 1
WHY? Element at i=1 is next smaller for index 0
Stack: []
Push 1
Stack: [1]
i=2, arr[2]=2
Stack: [1]
While: arr[1]=1 > 2? NO
WHY? 1 is not > 2
Stack: [1]
Push 2
Stack: [1, 2]
i=3, arr[3]=4
Stack: [1, 2]
While: arr[2]=2 > 4? NO
Stack: [1, 2]
Push 3
Stack: [1, 2, 3]
Handle remaining in stack:
Pop 3: right[3] = 4 - 3 = 1
Pop 2: right[2] = 4 - 2 = 2
Pop 1: right[1] = 4 - 1 = 3
Result: right = [1, 3, 2, 1]
═══════════════════════════════════════════════════════════
Calculate Contributions
═══════════════════════════════════════════════════════════
i=0: arr[0]=3, left[0]=1, right[0]=1
contribution = 3 × 1 × 1 = 3
Subarrays: [3]
i=1: arr[1]=1, left[1]=2, right[1]=3
contribution = 1 × 2 × 3 = 6
Subarrays: [1], [3,1], [1,2], [3,1,2], [1,2,4], [3,1,2,4]
(2 choices for start, 3 choices for end)
i=2: arr[2]=2, left[2]=1, right[2]=2
contribution = 2 × 1 × 2 = 4
Subarrays: [2], [2,4]
i=3: arr[3]=4, left[3]=1, right[3]=1
contribution = 4 × 1 × 1 = 4
Subarrays: [4]
Total = 3 + 6 + 4 + 4 = 17 ✓
Complexity Analysis
⏰ Time: O(n)
WHY O(n)?
Pass 1 (left boundaries):
Each element pushed once: n operations
Each element popped once: n operations (total)
Total: 2n = O(n)
Pass 2 (right boundaries):
Each element pushed once: n operations
Each element popped once: n operations (total)
Total: 2n = O(n)
Calculate contributions:
One loop: n operations
Overall: O(n) + O(n) + O(n) = O(n) ✓
Key: Amortized analysis
Even though we have while loops,
total pops across ALL iterations = n
💾 Space: O(n)
left array: O(n)
right array: O(n)
Stack: O(n) worst case
Total: O(n)
📊 Approach Comparison
┌────────────────────────────────────────────────────────┐
│ Approach 1 Approach 2 Approach 3 │
│ (All Subs) (Count L/R) (Stack) │
├────────────────────────────────────────────────────────┤
│ Idea Generate all Count extend Find │
│ subarrays left/right boundaries │
│ │
│ Time O(n²) O(n²) O(n) ✓ │
│ Generate Scan each Each element │
│ n² subarrays element once │
│ │
│ Space O(1) O(1) O(n) │
│ Arrays+stack │
│ │
│ Use? Never Never Always! ✓ │
└────────────────────────────────────────────────────────┘
🧪 Edge Cases
Edge Case 1: Single Element
arr = [5]
Subarrays: [5]
Sum = 5
left = [1] (no previous smaller)
right = [1] (no next smaller)
contribution = 5 × 1 × 1 = 5 ✓
Edge Case 2: All Same Elements
arr = [3, 3, 3]
Using >= left, > right:
Index 0: left=1, right=3 → 3×1×3 = 9
Index 1: left=1, right=2 → 3×1×2 = 6
Index 2: left=1, right=1 → 3×1×1 = 3
Total = 18
Verify:
[3],[3],[3] → 3+3+3 = 9
[3,3],[3,3] → 3+3 = 6
[3,3,3] → 3
Total = 18 ✓
Edge Case 3: Strictly Increasing
arr = [1, 2, 3, 4]
Each element's previous smaller is previous element
Each element's next smaller doesn't exist
Index 0: left=1, right=4 → 1×1×4 = 4
Index 1: left=1, right=3 → 2×1×3 = 6
Index 2: left=1, right=2 → 3×1×2 = 6
Index 3: left=1, right=1 → 4×1×1 = 4
Total = 20
Edge Case 4: Strictly Decreasing
arr = [4, 3, 2, 1]
Each element's previous smaller doesn't exist
Each element's next smaller is next element
Index 0: left=1, right=1 → 4×1×1 = 4
Index 1: left=2, right=1 → 3×2×1 = 6
Index 2: left=3, right=1 → 2×3×1 = 6
Index 3: left=4, right=1 → 1×4×1 = 4
Total = 20
⚠️ Common Mistakes
Mistake 1: Using same comparison for both directions
// ❌ WRONG - Both use >=
// Left: arr[stack.peek()] >= arr[i]
// Right: arr[stack.peek()] >= arr[i]
// This DOUBLE COUNTS duplicates!
// ✓ CORRECT - Different comparisons
// Left: arr[stack.peek()] >= arr[i] (or equal)
// Right: arr[stack.peek()] > arr[i] (strictly)
Mistake 2: Wrong distance calculation
// ❌ WRONG
left[i] = i - stack.peek() - 1;
// Off by one! Doesn't include element at stack.peek()
// ✓ CORRECT
left[i] = i - stack.peek();
// Correct distance
Mistake 3: Forgetting elements without next smaller
// ❌ WRONG - Only setting in while loop
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int idx = stack.pop();
right[idx] = i - idx;
}
// Stack might not be empty at end!
// ✓ CORRECT - Handle remaining
while (!stack.isEmpty()) {
int idx = stack.pop();
right[idx] = n - idx;
}
Mistake 4: Integer overflow
// ❌ WRONG
int contribution = arr[i] * left[i] * right[i];
// Can overflow for large values!
// ✓ CORRECT
long contribution = (long) arr[i] * left[i] * right[i];
total = (total + contribution) % MOD;
Mistake 5: Not clearing stack between passes
// ❌ WRONG
// First pass
for (int i = 0; i < n; i++) { ... }
// Second pass - stack still has elements!
for (int i = 0; i < n; i++) { ... }
// ✓ CORRECT
stack.clear(); // Clear between passes!
🎯 Pattern Recognition
This pattern appears when:
- Sum of minimums/maximums over all subarrays
- Contribution technique (each element contributes to answer)
- Need to count subarrays where element has a property
- Finding boundaries where property holds
Key Indicators:
- "Sum of min/max over all subarrays"
- "Count subarrays where element is min/max"
- "Contribution of each element"
- "Range where element dominates"
Similar Problems: - Sum of Subarray Ranges (LC 2104) - Maximum of Minimum Values (various) - Largest Rectangle in Histogram (next problem!) - Maximal Rectangle
📝 Quick Revision Notes
🎯 Core Concept
Instead of checking EVERY subarray, calculate each element's contribution: how many subarrays have it as minimum. Use monotonic stack to find boundaries (previous/next smaller). Contribution = arr[i] × left_count × right_count. Use >= for one direction, > for other to avoid double-counting duplicates.
⚡ Quick Implementation
import java.util.Stack;
class Solution {
public int sumSubarrayMins(int[] a) {
// Approach 1 - brute force
// Approach 2 - each element contribution
// Just FOLLOW this. Notes is little confusing.
// key concept: for every element, we need to find the number of subarrays in which it is minimum.
// For example, take [3,1,2,4]
// No of subarrays in which 1 is minimum: 1 (1-sized subarrays) + 2 (2-sized) + 2 (3-sized) + 1 (4-sized) = 6
// Thus, sum contributed by 1 = 1 * 6 = 6
// No of subarrays in which 3 is minimum: 1 + 0 + 0 + 0 = 1
// Sum contributed by 3 = 1 * 3 = 3
// No of subarrays in which 2 is minimum: 1 + 1 + 0 + 0 = 2
// Sum contributed by 2 = 2 * 2 = 4
// No of subarrays in which 4 is minimum: 1 + 0 + 0 + 0 = 1
// Sum contributed by 4 = 4
// Total = 6 + 3 + 4 + 4 = 17.
// If we go like this, we get O(N2)
// Lets again take 1 (index 1)
// Till what left index we can go where 1 is minimum: 0
// Till what right index we can go where 1 is minimum: 3
// Number of subbarays with 1 minimum: (1-0+1) * (3-1+1) = 6
// Now take 3 (index 0)
// Till what left index we can go where 3 is minimum: 0
// Till what right index we can go where 3 is minimum: 0
// Number of subbarays with 1 minimum: (0-0+1) * (0-0+1) = 1
// Now take 2 (index 2)
// Till what left index we can go where 2 is minimum: 2
// Till what right index we can go where 2 is minimum: 3
// Number of subbarays with 1 minimum: (2-2+1) * (3-2+1) = 2
// Now take 4 (index 3)
// Till what left index we can go where 4 is minimum: 3
// Till what right index we can go where 4 is minimum: 3
// Number of subbarays with 1 minimum: (3-3+1) * (3-3+1) = 1
// Ultimately, you need to find boundaries (next smaller elements) on
// left and right sides of every element.
// GOTCHA: for duplicates
int len = a.length;
int[] left = new int[len]; // [0,0,2,3] which is same as above explanation
int[] right = new int[len]; // [0,3,3,3] which is same as above explanation
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < len; i++) {
if(stack.isEmpty()) {
stack.push(i);
left[i] = i; // i itself
} else if(a[stack.peek()] < a[i]) {
// you found smaller element. Update left index boundary.
left[i] = i; // i itself
stack.push(i);
} else {
// pop till you find smaller element.
while (!stack.isEmpty() && a[stack.peek()] > a[i]) {
stack.pop();
}
// came out of above loop because stack became empty or found result.
if(stack.isEmpty()) {
left[i] = 0; // can extend complete left
} else {
left[i] = stack.peek() + 1;
}
stack.push(i);
}
}
// System.out.println(Arrays.toString(left));
// clear the existing stack
stack.clear();
for(int i = len - 1; i >= 0; i--) {
if(stack.isEmpty()) {
stack.push(i);
right[i] = i; // i itself
} else if(a[stack.peek()] < a[i]) {
// you found smaller element. Update left index boundary.
right[i] = i; // i itself
stack.push(i);
} else {
// pop till you find smaller element.
// GOTCHA: for duplicates
while (!stack.isEmpty() && a[stack.peek()] >= a[i]) {
stack.pop();
}
// came out of above loop because stack became empty or found result.
if(stack.isEmpty()) {
right[i] = len - 1; // can extend complete right
} else {
right[i] = stack.peek() - 1;
}
stack.push(i);
}
}
// System.out.println(Arrays.toString(right));
long res = 0;
int mod = 1000000007;
for(int i = 0; i < len; i++) {
res = res + (long)(i - left[i] + 1) * (right[i] - i + 1) * a[i];
}
return (int) (res % mod);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.sumSubarrayMins(new int[] {3,1,2,4}));
System.out.println(s.sumSubarrayMins(new int[] {11,81,94,43,3}));
}
}
🔑 Key Insights
Contribution Technique:
Don't enumerate subarrays!
Ask: "In how many subarrays is element i the minimum?"
Answer = left_count × right_count
Why Two Different Comparisons:
>= for left, > for right (or vice versa)
Prevents double-counting when duplicates exist!
Example: [2, 2]
First 2: claims [2,2]
Second 2: claims only [2] at its position
No overlap! ✓
Boundary Calculation:
left[i] = distance to previous smaller
= i - prev_smaller_index
= i + 1 if no previous smaller
right[i] = distance to next smaller
= next_smaller_index - i
= n - i if no next smaller
Time Complexity:
Two passes, each O(n):
- Each element pushed once
- Each element popped once
- Total pops = n across all iterations
Amortized O(1) per element!
Overall: O(n) ✓
🎪 Memory Aid
"Contribution = value × left × right"
"Use >= ONE way, > OTHER way"
"Stack finds boundaries efficiently"
"Each element pushed/popped ONCE!" ✨
⚠️ Don't Forget
- Use different comparisons (>= vs >) for duplicates
- Clear stack between passes
- Handle remaining elements in stack
- Use long for contribution (overflow!)
- Apply MOD to final sum
- left[i] = i + 1 if empty (not 0!)
- right[i] = n - i at end (not n!)
🔗 Connection to Other Problems
Daily Temperatures: Find next greater (one direction)
Stock Span: Find previous greater (one direction)
This Problem: Find BOTH directions (boundaries!)
Same monotonic stack technique,
but applied to find ranges!
Happy coding! This is a beautiful example of the contribution technique with monotonic stacks! 🚀