#907
Sum of Subarray Minimums
Medium Monotonic stack contribution
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sum the minimum of every contiguous subarray, modulo 1e9+7.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: add up the minimum of every subarray.
Why this works: count how many subarrays have arr[i] as their minimum: (distance to previous smaller) × (distance to next smaller-or-equal).
Example: [3, 1, 2, 4]
3: 1×1 → 3, 1: 2×3 → 6, 2: 1×2 → 4, 4: 1×1 → 4total 17
✦Hints open one at a time
Instead of looping over subarrays, ask: in how many subarrays is arr[i] the minimum?
That's (distance to the previous smaller element) × (distance to the next smaller-or-equal element).
Use strict on one side and non-strict on the other so equal values aren't counted twice.
↗Approach
Use a monotonic increasing stack. When an index is popped by a smaller-or-equal value at i, its next boundary is i and its previous boundary is the new stack top. Add arr[mid] × left × right. A sentinel pass at i = n flushes the stack.
</>Solution (Java)
import java.util.*;
class Solution {
public int sumSubarrayMins(int[] arr) {
final long MOD = 1_000_000_007L;
int n = arr.length;
Deque<Integer> st = new ArrayDeque<>();
long sum = 0;
for (int i = 0; i <= n; i++) {
int cur = (i == n) ? Integer.MIN_VALUE : arr[i]; // sentinel flushes the stack
while (!st.isEmpty() && arr[st.peek()] >= cur) {
int mid = st.pop();
int left = mid - (st.isEmpty() ? -1 : st.peek()); // choices for the start
int right = i - mid; // choices for the end
sum = (sum + (long) arr[mid] * left * right) % MOD;
}
st.push(i);
}
return (int) sum;
}
}!Common mistake
Using strict < on both sides, which double-counts subarrays with repeated minimums.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon