Sum of Subarray Minimums — The Contribution Technique with Monotonic Stacks

Problem Statement#

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.

Constraints:

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

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

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

Why This Problem Matters#

Sum of Subarray Minimums introduces one of the most powerful techniques in competitive programming: the contribution technique (also called "count the contribution of each element"). Instead of iterating over all subarrays and finding their minimum (O(n²)), flip the question: for each element, how many subarrays is it the minimum of? Multiply by the element value and sum. This technique appears in Sum of Subarray Ranges (LC 2104), Maximum Sum of Subarray Min-Product (LC 1856), and many harder problems.

Google and Amazon use this problem to test two things simultaneously: the contribution counting insight AND the monotonic stack implementation to find previous/next smaller element boundaries in O(n). Both pieces must come together cleanly.

The modulo handling (10^9 + 7) is a common source of bugs — interviewers watch for whether you apply modulo only at the end (wrong for large inputs) or at each multiplication step.

The Core Insight#

For each element arr[i], define:

• left[i] = number of contiguous elements to the left including arr[i] until a strictly smaller element is found (or the array starts)
• right[i] = number of contiguous elements to the right including arr[i] until a smaller or equal element is found (or the array ends)

Number of subarrays where arr[i] is the minimum = left[i] * right[i].

Why use "strictly smaller" for the left and "smaller or equal" for the right? To avoid double-counting when equal elements both claim the same subarray's minimum. This asymmetry ensures each subarray is claimed by exactly one element.

Contribution of arr[i] = arr[i] * left[i] * right[i].

Visual Dry Run#

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

Left pass (previous strictly smaller element):

• i=0, arr=3: no previous smaller, left[0] = 1
• i=1, arr=1: no previous strictly smaller (3>=1), left[1] = 2
• i=2, arr=2: previous strictly smaller is 1 at index 1, left[2] = 1
• i=3, arr=4: previous strictly smaller is 2 at index 2, left[3] = 1

Right pass (next smaller or equal element):

• right = [1, 3, 2, 1]

Contributions:

• i=0: 3 * 1 * 1 = 3
• i=1: 1 * 2 * 3 = 6
• i=2: 2 * 1 * 2 = 4
• i=3: 4 * 1 * 1 = 4

Total = 3 + 6 + 4 + 4 = 17. Correct.

Solution (Optimal)#

class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        left = [0] * n
        right = [0] * n
        stack = []
 
        # left[i]: distance to previous strictly smaller element
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            left[i] = i + 1 if not stack else i - stack[-1]
            stack.append(i)
 
        stack = []
 
        # right[i]: distance to next smaller or equal element
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            right[i] = n - i if not stack else stack[-1] - i
            stack.append(i)
 
        return sum(arr[i] * left[i] * right[i] for i in range(n)) % MOD

var sumSubarrayMins = function(arr) {
    const MOD = 1_000_000_007n;
    const n = arr.length;
    const left = new Array(n).fill(0);
    const right = new Array(n).fill(0);
    let stack = [];
 
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        left[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
        stack.push(i);
    }
 
    stack = [];
 
    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 ? n - i : stack[stack.length - 1] - i;
        stack.push(i);
    }
 
    let result = 0n;
    for (let i = 0; i < n; i++) {
        result = (result + BigInt(arr[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;
    }
 
    return Number(result);
};

Time: O(n) — two stack passes, each O(n) Space: O(n) — left[], right[], and stack

Common Mistakes#

• Using the same inequality for both left and right passes — left uses >= (pop equal elements, strict smaller for boundary); right uses > (pop strictly greater, allow equal elements as right boundary); swapping these creates double-counting
• Applying modulo at the wrong place — in Python, multiply large integers then take modulo at the end of the sum; in JavaScript use BigInt or apply modulo after each multiplication to avoid overflow
• Wrong left[i] formula — when stack is empty: left[i] = i + 1 (all elements from 0 to i are in the domain); when stack has remaining element at index j: left[i] = i - j

Interview Tips#

• Immediately identify the contribution technique: "Instead of computing the minimum of each subarray, I flip the problem — for each element, count how many subarrays have it as the minimum, then multiply and sum."
• Explain duplicate handling: "I use strict inequality on one side (left) and non-strict on the other (right), so each subarray's minimum is claimed by exactly one element."
• Walk through the left[i] formula on a small example before coding — interviewers often ask "what does left[i] represent exactly?"

Follow-up Questions#

• How do you find the sum of subarray maximums instead? Use the same contribution technique but with a decreasing stack. left[i] = distance to previous strictly larger; right[i] = distance to next larger or equal.
• How do you find the sum of (max - min) over all subarrays (LC 2104)? Compute sum of subarray maximums and sum of subarray minimums separately, then subtract.
• What if you need the sum of the k-th smallest in each subarray? This is significantly harder and requires order-statistics trees or persistent segment trees.

Key Takeaways#

• The contribution technique flips "find minimum of each subarray" to "count subarrays where each element is the minimum."
• Two monotonic stack passes compute left and right domain sizes in O(n) — left pass uses strict inequality, right pass uses non-strict.
• The asymmetric inequality (strict left, non-strict right) avoids double-counting when equal elements exist.
• Apply modulo after each multiplication in languages without arbitrary precision integers to prevent overflow.
• The final answer is sum(arr[i] * left[i] * right[i] for all i) % MOD.
• This technique generalizes to sum of subarray maximums, sum of subarray ranges, and maximum subarray min-product problems.
• The brute force O(n²) and this O(n) differ by flipping the question from "for each subarray, find its min" to "for each element, count the subarrays it is min of."