Sum of Subarray Minimums — Monotonic Stack Contribution Counting

Problem Statement#

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

Constraints:

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

Input:  arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays: [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

Input:  arr = [11,81,94,43,3]
Output: 444

Input:  arr = [1]
Output: 1

Why This Problem Matters#

LC 907 teaches the contribution technique — a powerful approach where instead of iterating over all subarrays and computing their minimum, you flip the perspective: for each element, count how many subarrays have it as the minimum, then multiply by its value.

This "contribution counting + monotonic stack" pattern appears in:

• Largest Rectangle in Histogram (LC 84) — contribution of each bar's height.
• Maximum Width Ramp (LC 962) — contribution of each element's position.
• Sum of Subarray Ranges (LC 2104) — sum of max minus min for all subarrays.
• Many competitive programming problems involving subarray extremes.

The problem is a medium but requires deep thinking about the monotonic stack, boundary conditions (handling duplicates), and modular arithmetic. It is asked at Google and Amazon, often as a warm-up for the harder LC 84 (Largest Rectangle).

The Core Insight#

Brute force: Enumerate all O(n^2) subarrays and find the minimum of each. O(n^3) time (or O(n^2) with incremental min tracking). Too slow for n = 3*10^4.

Contribution technique: For each element arr[i], compute how many subarrays have arr[i] as their minimum. Then the contribution of arr[i] to the total sum is arr[i] * count.

For element i to be the minimum of a subarray [l, r], the subarray must not contain any element smaller than arr[i]. This means:

• The left boundary extends to the previous element smaller than arr[i] (exclusive). Let left[i] = number of elements to the left (including i itself) until a strictly smaller element.
• The right boundary extends to the next element smaller than or equal to arr[i] (exclusive). Let right[i] = number of elements to the right (including i itself) until a smaller-or-equal element.

Contribution: arr[i] * left[i] * right[i]

The asymmetry (strict vs strict-or-equal) is intentional to avoid double-counting subarrays where two equal minimums exist.

Visual Dry Run#

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

Previous smaller (strict <):

• arr[0]=3: no previous → left boundary at -1. left[0] = 0 - (-1) = 1.
• arr[1]=1: no previous smaller → left[1] = 1 - (-1) = 2.
• arr[2]=2: previous smaller is arr[1]=1. left[2] = 2 - 1 = 1.
• arr[3]=4: previous smaller is arr[2]=2. left[3] = 3 - 2 = 1.

Next smaller or equal (<=):

• arr[0]=3: next smaller/equal is arr[1]=1. right[0] = 1 - 0 = 1.
• arr[1]=1: no next smaller/equal → right boundary at n=4. right[1] = 4 - 1 = 3.
• arr[2]=2: no next smaller/equal → right[2] = 4 - 2 = 2.
• arr[3]=4: no next smaller/equal → right[3] = 4 - 3 = 1.

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

Solution (Optimal)#

# Python — two-pass monotonic stack for contribution counting, O(n) time
def sumSubarrayMins(arr: list[int]) -> int:
    MOD = 10**9 + 7
    n = len(arr)
 
    # left[i] = distance from i to previous strictly smaller element
    # Equivalently: how many consecutive elements to the left where arr[i] is the minimum
    left = [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 -1)
        stack.append(i)
 
    # right[i] = distance from i to next smaller or equal element
    # Asymmetric to avoid double-counting equal minimums
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = (stack[-1] if stack else n) - i
        stack.append(i)
 
    # Sum contributions
    return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD

// JavaScript — two-pass monotonic stack, O(n) time
function sumSubarrayMins(arr) {
    const MOD = 1_000_000_007n;  // BigInt for mod arithmetic
    const n = arr.length;
    const left = new Array(n).fill(0);
    const right = new Array(n).fill(0);
    const stack = [];
 
    // Previous strictly smaller element
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        left[i] = i - (stack.length > 0 ? stack[stack.length - 1] : -1);
        stack.push(i);
    }
 
    stack.length = 0;  // clear stack
 
    // Next smaller or equal element
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] > arr[i]) {
            stack.pop();
        }
        right[i] = (stack.length > 0 ? stack[stack.length - 1] : n) - i;
        stack.push(i);
    }
 
    let ans = 0n;
    for (let i = 0; i < n; i++) {
        ans = (ans + BigInt(arr[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;
    }
    return Number(ans);
}

Complexity:

Common Mistakes#

1. Using strict less-than in both directions. The asymmetry — strict < for the left boundary, strict-or-equal <= for the right boundary — is crucial for avoiding double-counting when duplicate elements exist. Using strict < for both directions counts subarrays with equal minimums twice.

2. Overflow in multiplication. arr[i] * left[i] * right[i] can overflow a 32-bit integer (arr[i] up to 310^4, left/right up to n = 310^4 each → product up to 2.7*10^13). Use 64-bit integers (long in Java, BigInt in JavaScript, Python's arbitrary-precision integers handle it automatically).

3. Off-by-one in left/right computation. left[i] = i - prev_smaller_idx where prev_smaller_idx = -1 if none exists. right[i] = next_smaller_idx - i where next_smaller_idx = n if none exists. Getting the sentinel values wrong shifts contributions by 1.

4. Not using modular arithmetic until the final sum. Since contributions can overflow, take modulo at each addition, not just at the very end.

5. Single-pass variant: confusing the stack entry type. Some single-pass implementations store (value, contribution) pairs. The two-pass approach with separate left/right arrays is easier to reason about and debug.

Interview Tips#

• State the contribution insight: "Instead of iterating over all subarrays to find each minimum, I flip the question: for each element, how many subarrays have it as the minimum? Multiplying by value gives the contribution."
• Explain the asymmetry: "To avoid double-counting when duplicate values exist, I use strict inequality for one direction and non-strict for the other. Previous strictly smaller vs next smaller-or-equal."
• Mention overflow: "The product can reach 310^4 * 310^4 * 310^4 ≈ 2.710^13, which overflows 32-bit integers. Use 64-bit or modular arithmetic throughout."

Follow-up Questions#

1. Sum of Subarray Maximums. Same approach with a monotonic decreasing stack (find previous/next larger elements).
2. Sum of Subarray Ranges (LC 2104) — sum of max(b) - min(b) for all subarrays. Combine the min and max contribution approaches.
3. Largest Rectangle in Histogram (LC 84) — same contribution idea: each bar's height is the minimum in a set of subarrays.
4. What if the array has all equal elements? The contribution counts correctly — the asymmetric boundary condition handles equal elements without double-counting.
5. Sum of subarray k-th minimums. Use a min-heap or order statistics tree alongside the contribution counting framework.

Key Takeaways#

• Contribution technique: for each element, compute how many subarrays have it as the minimum, then sum value * count. This flips the problem from iterating subarrays to iterating elements.
• left[i] = distance to previous strictly smaller element; right[i] = distance to next smaller or equal element. The asymmetry prevents double-counting duplicates.
• Use 64-bit arithmetic throughout — intermediate products can reach ~10^13, well above 32-bit overflow threshold.
• Two monotonic stack passes (one forward, one backward) compute left and right arrays in O(n) total.
• This pattern of "contribution per element via previous/next smaller" also powers Largest Rectangle in Histogram (LC 84) and Sum of Subarray Ranges (LC 2104).
• In interviews, state the invariant and contribution formula before coding — it demonstrates advanced pattern recognition beyond the basic monotonic stack application.