Sum of Subarray Minimums — Contribution Technique with Stack (LeetCode 907)

Sum of Subarray Minimums (LeetCode 907) is one of the best problems for mastering monotonic stacks. Instead of finding the minimum of every subarray (O(n^2)), you flip the question: for each element, how many subarrays is it the minimum of?

The Problem

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

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

Subarrays and their minimums:
[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

Brute Force — O(n^2)

def sum_subarray_mins_brute(arr):
    """Enumerate all subarrays — O(n^2)."""
    MOD = 10**9 + 7
    n = len(arr)
    total = 0
    for i in range(n):
        curr_min = arr[i]
        for j in range(i, n):
            curr_min = min(curr_min, arr[j])
            total = (total + curr_min) % MOD
    return total

The Contribution Technique

Instead of computing the minimum of each subarray, ask: for element arr[i], how many subarrays have arr[i] as their minimum?

If arr[i] is the minimum of a subarray arr[L..R], then:

• L can be anything from the previous smaller element’s index + 1 to i
• R can be anything from i to the next smaller-or-equal element’s index - 1

The number of such subarrays = left_count * right_count, where:

• left_count = distance from i to the previous strictly smaller element (or start of array)
• right_count = distance from i to the next smaller-or-equal element (or end of array)

The total contribution of arr[i] = arr[i] * left_count * right_count.

Why Strict on One Side, Non-Strict on the Other?

When there are duplicate values, we must avoid double-counting. Consider [1, 2, 1]:

• The subarray [1, 2, 1] has minimum 1, but which 1 “owns” it?

We break ties by using:

• Strictly smaller on the left (<)
• Smaller or equal on the right (<=)

This means the leftmost duplicate owns subarrays containing both. Each subarray is counted exactly once.

Python Implementation

def sum_subarray_mins(arr):
    """
    Contribution technique with monotonic stacks.
    Time: O(n) — two passes for prev/next smaller.
    Space: O(n) — for stacks and boundary arrays.
    """
    MOD = 10**9 + 7
    n = len(arr)

    # Previous smaller element index (strict <)
    prev_smaller = [-1] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        prev_smaller[i] = stack[-1] if stack else -1
        stack.append(i)

    # Next smaller or equal element index (<= for tie-breaking)
    next_smaller_eq = [n] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        next_smaller_eq[i] = stack[-1] if stack else n
        stack.append(i)

    # Compute contributions
    total = 0
    for i in range(n):
        left = i - prev_smaller[i]      # count of left choices
        right = next_smaller_eq[i] - i   # count of right choices
        total = (total + arr[i] * left * right) % MOD

    return total

Step-by-Step Trace

For arr = [3, 1, 2, 4]:

Step 1: Find previous smaller (strict <)

i=0, val=3: stack=[]     → prev_smaller[0]=-1, push 0
i=1, val=1: pop 0 (3>=1) → prev_smaller[1]=-1, push 1
i=2, val=2: stack=[1]    → prev_smaller[2]=1, push 2
i=3, val=4: stack=[1,2]  → prev_smaller[3]=2, push 3

prev_smaller = [-1, -1, 1, 2]

Step 2: Find next smaller or equal (right to left, > for popping)

i=3, val=4: stack=[]     → next_smaller_eq[3]=4, push 3
i=2, val=2: pop 3 (4>2)  → next_smaller_eq[2]=4, push 2
i=1, val=1: pop 2 (2>1)  → next_smaller_eq[1]=4, push 1
i=0, val=3: stack=[1]    → next_smaller_eq[0]=1, push 0

next_smaller_eq = [1, 4, 4, 4]

Step 3: Compute contributions

i=0: left = 0-(-1) = 1, right = 1-0 = 1
     contribution = 3 * 1 * 1 = 3

i=1: left = 1-(-1) = 2, right = 4-1 = 3
     contribution = 1 * 2 * 3 = 6

i=2: left = 2-1 = 1, right = 4-2 = 2
     contribution = 2 * 1 * 2 = 4

i=3: left = 3-2 = 1, right = 4-3 = 1
     contribution = 4 * 1 * 1 = 4

Total = 3 + 6 + 4 + 4 = 17 ✓

Understanding Left and Right Counts

For element arr[1] = 1 with prev_smaller[1] = -1 and next_smaller_eq[1] = 4:

• Left choices: the subarray can start at index 0 or 1 (2 choices)
• Right choices: the subarray can end at index 1, 2, or 3 (3 choices)
• Total subarrays where arr[1]=1 is the minimum: 2 * 3 = 6
• Those subarrays: [3,1], [1], [3,1,2], [1,2], [3,1,2,4], [1,2,4]
• All have minimum 1 ✓

Handling Duplicates: A Detailed Example

For arr = [1, 2, 1]:

prev_smaller (strict <):  [-1, 0, -1]
  For i=2, val=1: pop 1 (2>=1), pop 0 (1>=1) → -1

next_smaller_eq (<=):  [2, 2, 3]
  For i=0, val=1: stack=[2], arr[2]=1, 1 > 1? No → next[0]=2

Contributions:
  i=0: left=1, right=2-0=2 → 1*1*2 = 2
  i=1: left=1-0=1, right=2-1=1 → 2*1*1 = 2
  i=2: left=2-(-1)=3, right=3-2=1 → 1*3*1 = 3

Total = 2 + 2 + 3 = 7

Verification: [1]=1, [2]=2, [1]=1, [1,2]=1, [2,1]=1, [1,2,1]=1
Sum = 1+2+1+1+1+1 = 7 ✓

Notice how [1,2,1] with minimum 1 is “owned” by the rightmost 1 (i=2), not the leftmost, due to our strict/non-strict tie-breaking.

Modular Arithmetic

The problem asks for the answer mod 10^9 + 7. Since we only use addition and multiplication, we can take mod at each step:

total = (total + arr[i] * left * right) % MOD

This prevents integer overflow (important in languages like C++ and Java; Python handles big integers natively, but taking mod is still required for the correct answer).

Edge Cases

1. Single element — [5] → 5
2. All same elements — [3, 3, 3] → 3+3+3+3+3+3 = 18
3. Sorted ascending — [1, 2, 3] → each element’s left count is 1
4. Sorted descending — [3, 2, 1] → each element’s right count is 1
5. Large array — up to 30,000 elements, must be O(n)

Complexity Analysis

Metric	Value
Time	O(n) — three linear passes
Space	O(n) — boundary arrays and stacks

When to Use This Pattern

Use the contribution technique when:

• You need the sum (or count) of some property across all subarrays
• The property is defined by a single element per subarray (min, max, etc.)
• You can find boundaries using monotonic stacks
• The problem says “mod 10^9+7” (hinting at large answer, needs efficient approach)

Related Problems

Problem	Difficulty	Key Idea
LeetCode 907 — Sum of Subarray Minimums	Medium	This problem
LeetCode 2104 — Sum of Subarray Ranges	Medium	Sum of max - sum of min
LeetCode 84 — Largest Rectangle in Histogram	Hard	Contribution of each bar
LeetCode 85 — Maximal Rectangle	Hard	Build on histogram
LeetCode 1856 — Maximum Subarray Min-Product	Medium	Min * sum with boundaries

Key Takeaway

Sum of Subarray Minimums teaches the contribution technique — instead of iterating over all subarrays, compute each element’s contribution by finding its left and right boundaries using monotonic stacks. The strict-vs-non-strict comparison for tie-breaking is the subtle detail that makes or breaks correctness with duplicates.