Sum of Subarray Minimums LeetCode 907

LeetCode 907 — Sum of Subarray Minimums — gives you an array of integers arr. For every contiguous subarray, find the minimum element, then return the sum of all these minimums modulo 10^9 + 7.

The brute force approach considers all O(n^2) subarrays and finds each minimum in O(n) time, giving O(n^3) total. Even with optimization to O(n^2), this is too slow for n up to 30,000. We need a fundamentally different perspective.

The key insight is the contribution technique: instead of asking "what is the minimum of each subarray?", ask "for each element, how many subarrays is it the minimum of?" If arr[i] is the minimum of exactly C subarrays, it contributes arr[i] * C to the total sum.

For element arr[i] to be the minimum of a subarray arr[l..r], every element in that range must be >= arr[i]. This means l cannot extend past the previous smaller element (PLE), and r cannot extend past the next smaller element (NLE).

Let left[i] be the number of consecutive elements to the left of i (including i) that are >= arr[i]. Let right[i] be the count to the right. Then arr[i] is the minimum of exactly left[i] * right[i] subarrays: we can choose any starting point from i-left[i]+1 to i, and any ending point from i to i+right[i]-1.

The total contribution of arr[i] is arr[i] * left[i] * right[i]. Sum all contributions and take mod 10^9 + 7. The challenge reduces to computing left[i] and right[i] efficiently for every index.

A monotonic increasing stack efficiently finds the previous less element for every index. Scan left to right: for each arr[i], pop elements from the stack while the top is >= arr[i]. The new top (after popping) is the PLE. Push i onto the stack. left[i] = i - PLE_index.

For the next less element, scan right to left with a similar monotonic stack. For each arr[i], pop while the top is > arr[i] (note: strictly greater to handle duplicates). The new top is the NLE. right[i] = NLE_index - i. If the stack is empty, use n as the boundary.

Both passes run in O(n) time because each element is pushed and popped at most once. Combined with the contribution sum, the entire algorithm is O(n) time and O(n) space for the stack and auxiliary arrays.

Consider arr = [3, 1, 2, 4]. Find PLE (previous less element) for each index. i=0: stack empty, PLE = -1, left[0] = 0-(-1) = 1. i=1: pop 3 (>=1), stack empty, PLE = -1, left[1] = 1-(-1) = 2. i=2: top is 1 (<2), PLE = 1, left[2] = 2-1 = 1. i=3: top is 2 (<4), PLE = 2, left[3] = 3-2 = 1.

Find NLE (next less or equal element) scanning right to left. i=3: stack empty, NLE = 4, right[3] = 4-3 = 1. i=2: top is 4 (>2), pop. Stack empty, NLE = 4, right[2] = 4-2 = 2. i=1: stack has 2 (>1), pop. Stack empty, NLE = 4, right[1] = 4-1 = 3. i=0: stack has 1 (<=3? 1<3 yes), NLE = 1, right[0] = 1-0 = 1.

Contributions: arr[0]*1*1 = 3, arr[1]*2*3 = 6, arr[2]*1*2 = 4, arr[3]*1*1 = 4. Total = 3 + 6 + 4 + 4 = 17. Verify: subarrays are [3]→3, [1]→1, [2]→2, [4]→4, [3,1]→1, [1,2]→1, [2,4]→2, [3,1,2]→1, [1,2,4]→1, [3,1,2,4]→1. Sum = 3+1+2+4+1+1+2+1+1+1 = 17.

In Python, use a list as the stack. Two passes: left-to-right for left[] and right-to-left for right[]. Then compute the sum with sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD. The modular arithmetic only needs to be applied at the final sum.

In Java, use an ArrayDeque<Integer> as the stack. Store indices, not values. The two-pass approach is identical. Accumulate the sum in a long to avoid overflow before taking mod. Each contribution arr[i] * left[i] * right[i] can exceed int range.

A single-pass variant exists: process the contribution when popping from the stack rather than using separate left[] and right[] arrays. When you pop index j because arr[i] < arr[j], the contribution of arr[j] is arr[j] * (j - stack.peek()) * (i - j). This is more compact but harder to debug.

Time complexity is O(n). Each element is pushed onto and popped from the stack at most once across both passes. The contribution summation is a single O(n) loop. Total operations are bounded by 4n.

Space complexity is O(n) for the stack, the left[] array, and the right[] array. The single-pass variant reduces auxiliary arrays but still uses O(n) stack space. In-place approaches are not possible because we need the stack to track boundaries.

This is optimal — we must read every element at least once, and the monotonic stack processes each element exactly twice (one push, one pop). The contribution technique eliminates the need to enumerate all O(n^2) subarrays.

Largest Rectangle in Histogram (LeetCode 84) is the classic monotonic stack problem. It uses the same PLE/NLE technique to find how far each bar extends. Sum of Subarray Minimums applies the same boundaries but sums contributions instead of maximizing area.

Sum of Subarray Ranges (LeetCode 2104) extends this problem by computing sum(max) - sum(min) for all subarrays. You run the monotonic stack twice: once for minimums (increasing stack) and once for maximums (decreasing stack), then subtract.

Daily Temperatures (LeetCode 739) and Next Greater Element (LeetCode 496) are simpler monotonic stack problems that build intuition for the stack invariant. Master these before tackling the contribution technique problems.