Sum of Subarray Minimums: Monotonic Stack Contribution Technique

LeetCode 907 Sum of Subarray Minimums is a beautiful example of the "contribution technique." Instead of examining every subarray and finding its minimum, you flip the question: for each element, how many subarrays have it as the minimum? Once you know that count, you can compute the answer in O(n) time using a monotonic stack.

The problem

Given an array of integers arr, find the sum of min(b) for every contiguous subarray b of arr. Return the answer modulo 10^9 + 7.

Input:  arr = [3, 1, 2, 4]
Output: 17

There are 10 subarrays total. You take the minimum of each one and sum them up.

The brute force is to enumerate all O(n^2) subarrays, find each minimum in O(n), and sum them. That is O(n^3), or O(n^2) with some optimization. But the array can have up to 30,000 elements, so we need O(n).

The key insight: contribution counting

Instead of asking "what is the minimum of subarray [i..j]?", ask the reverse: "for element arr[i], how many subarrays have arr[i] as their minimum?"

If you can answer that for every index, then the total sum is simply:

sum of arr[i] * count[i] for all i

The trick is computing count[i] efficiently. This is where the monotonic stack comes in.

Finding left and right boundaries

For arr[i] to be the minimum of a subarray, that subarray cannot extend past a smaller element. So you need two pieces of information:

1. left[i]: how far left can a subarray extend while arr[i] remains the minimum? This is the distance from i to the previous element that is strictly smaller.
2. right[i]: how far right can a subarray extend? This is the distance from i to the next element that is smaller or equal.

The number of subarrays where arr[i] is the minimum equals left[i] * right[i]. The left boundary gives you the number of valid starting points, and the right boundary gives the number of valid ending points.

Why "strictly smaller" on the left but "smaller or equal" on the right? To avoid double-counting. If two elements have the same value, you need a consistent tiebreaker. Using strict on one side and non-strict on the other ensures each subarray is counted exactly once.

The algorithm

Two passes with a monotonic stack:

Left pass (left to right): For each index i, pop all elements from the stack that are greater than or equal to arr[i]. The remaining top gives the previous strictly smaller element. If the stack is empty, the boundary extends all the way to the start.

Right pass (right to left): For each index i, pop all elements from the stack that are strictly greater than arr[i]. The remaining top gives the next smaller-or-equal element. If the stack is empty, the boundary extends to the end.

After both passes, compute the answer as the sum of arr[i] * left[i] * right[i] for all i.

The code

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)
    result = 0
    for i in range(n):
        result = (result + arr[i] * left[i] * right[i]) % MOD
    return result

The first loop computes left boundaries. The condition arr[stack[-1]] >= arr[i] pops elements that are greater or equal, so the remaining top (if any) is strictly smaller. The second loop computes right boundaries with arr[stack[-1]] > arr[i], popping only strictly greater elements. This asymmetry handles duplicates correctly.

Step-by-step walkthrough

Let's trace through arr = [3, 1, 2, 4]. We perform two passes: a left pass scanning left to right and a right pass scanning right to left. The L values show how many positions to the left each element dominates. The R values show positions to the right.

Notice the final step: once you have left and right arrays, the contribution of each element is just a multiplication. Element 1 at index 1 has left=2 and right=3, meaning it is the minimum of 23=6 subarrays. Its contribution is 16=6, which accounts for a big chunk of the answer.

Complexity analysis

Time: O(n). Each index is pushed onto the stack once and popped at most once in each pass. Two passes of O(n) each give O(n) total.

Space: O(n). The stack, left array, and right array each use O(n) space.

The building blocks

This problem combines two reusable patterns:

Monotonic stack for boundaries

The core loop for finding the previous smaller element:

stack = []
for i in range(n):
    while stack and arr[stack[-1]] >= arr[i]:
        stack.pop()
    left[i] = i - stack[-1] if stack else i + 1
    stack.append(i)

This is the same pattern used in Daily Temperatures, Largest Rectangle in Histogram, and Online Stock Span. The only differences are the comparison direction and what you compute when popping.

Contribution counting

Once you have the boundaries, the final accumulation is:

result = sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD

This pattern of "count how many substructures each element participates in" appears in many sum-over-subarrays problems.

Edge cases

Before submitting, verify your solution handles:

• All equal elements like [5, 5, 5, 5]: each element is the minimum of some subarrays. The asymmetric comparison (>= left, > right) prevents double-counting.
• Strictly increasing like [1, 2, 3, 4]: element at index 0 is the minimum of all subarrays that include it (4 subarrays). Each subsequent element has a smaller left boundary.
• Strictly decreasing like [4, 3, 2, 1]: element at index 3 is the minimum of all 4 subarrays that include it.
• Single element [7]: answer is 7. left[0]=1, right[0]=1, contribution = 7.
• Large values with modulo: the problem specifies mod 10^9 + 7. Apply the modulo at each accumulation step to prevent overflow.

From understanding to recall

You now understand how the contribution technique works with a monotonic stack. The algorithm has three parts: left pass, right pass, accumulation. Each part is short, but the details matter. The asymmetric comparison (>= versus >) is easy to mix up under pressure. The direction of the right pass (iterating backwards) is another detail that trips people up.

Spaced repetition helps lock in these details. Instead of re-reading this explanation in three weeks when you see a similar problem, you practice writing the two-pass boundary code from scratch at increasing intervals. After a few repetitions, the asymmetric comparison becomes second nature and you can focus on recognizing when contribution counting applies.

Related posts

• Daily Temperatures - The classic introduction to monotonic stacks, using the same pop-when-smaller pattern
• Largest Rectangle in Histogram - Uses the same left/right boundary technique to compute widths for each bar height
• Online Stock Span - Another monotonic stack problem that tracks how far each element dominates

CodeBricks breaks the monotonic stack and contribution technique into their reusable pieces and drills them individually. You type the boundary loops from scratch each time, building the muscle memory so that when you see a sum-over-subarrays problem in an interview, the code flows without hesitation.