907. Sum of Subarray Minimums (Medium)

Problem

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

Examples

• [3,1,2,4] → 17
  • Subarrays and their minimums:
  • [3]=3, [3,1]=1, [3,1,2]=1, [3,1,2,4]=1
  • [1]=1, [1,2]=1, [1,2,4]=1
  • [2]=2, [2,4]=2
  • [4]=4
  • Sum: 3+1+1+1+1+1+1+2+2+4 = 17
• [11,81,94,43,3] → 444

LeetCode 907 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, enumerate all subarrays

Try every starting index, extend to the right tracking the running minimum.

Python

def sum_subarray_mins(arr: list[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(arr)
    total = 0
    for i in range(n):                      # L1: n iterations
        cur_min = arr[i]
        for j in range(i, n):               # L2: up to n-i iterations
            cur_min = min(cur_min, arr[j])  # L3: O(1) track running min
            total = (total + cur_min) % MOD # L4: O(1) accumulate
    return total

TypeScript

function sumSubarrayMins(arr: number[]): number {
    const MOD = 1_000_000_007;
    const n = arr.length;
    let total = 0;
    for (let i = 0; i < n; i++) {               // L1: n iterations
        let curMin = arr[i];
        for (let j = i; j < n; j++) {           // L2: up to n-i iterations
            curMin = Math.min(curMin, arr[j]);   // L3: O(1) track running min
            total = (total + curMin) % MOD;      // L4: O(1) accumulate
        }
    }
    return total;
}

Swift

final class Solution {
    func sumSubarrayMins(_ arr: [Int]) -> Int {
        let modulus = 1_000_000_007
        var total = 0
        for left in arr.indices {
            var minimum = arr[left]
            for right in left..<arr.count { minimum = min(minimum, arr[right]); total = (total + minimum) % modulus }
        }
        return total
    }
}

Complexity

• Time: $O(n²)$, nested loops each running up to n.
• Space: $O(1)$ extra.

Approach 2: Contribution counting with monotonic stack (optimal)

Instead of iterating subarrays, ask: how many subarrays have arr[i] as their minimum? The contribution of element i is arr[i] * left[i] * right[i], where:

• left[i] = number of elements from i going left until hitting a strictly smaller element (or the array boundary). This is the distance to the previous smaller element.
• right[i] = number of elements from i going right until hitting a smaller-or-equal element. This is the distance to the next smaller or equal element.

The asymmetry (strict left, non-strict right) prevents double-counting when equal elements are adjacent.

Python

def sum_subarray_mins(arr: list[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(arr)
    left = [0] * n   # left[i]: distance to previous strictly smaller (or left edge)
    right = [0] * n  # right[i]: distance to next smaller-or-equal (or right edge)
    stack = []        # monotonic stack of indices

    for i in range(n):                            # L1: compute left spans
        while stack and arr[stack[-1]] >= arr[i]: # L2: pop while not strictly smaller
            stack.pop()                           # L3: O(1) amortized
        left[i] = i - stack[-1] if stack else i + 1  # L4: O(1) distance from left
        stack.append(i)                           # L5: O(1) push

    stack = []
    for i in range(n - 1, -1, -1):               # L6: compute right spans (right to left)
        while stack and arr[stack[-1]] > arr[i]:  # L7: pop while strictly greater
            stack.pop()                           # L8: O(1) amortized
        right[i] = stack[-1] - i if stack else n - i  # L9: O(1) distance to right
        stack.append(i)                           # L10: O(1) push

    total = 0
    for i in range(n):                            # L11: sum contributions
        total = (total + arr[i] * left[i] * right[i]) % MOD  # L12: O(1)
    return total

TypeScript

function sumSubarrayMins(arr: number[]): number {
    const MOD = 1_000_000_007n;
    const n = arr.length;
    const left = new Array(n).fill(0);    // left[i]: distance to previous strictly smaller
    const right = new Array(n).fill(0);   // right[i]: distance to next smaller-or-equal
    let stack: number[] = [];

    for (let i = 0; i < n; i++) {                        // L1: compute left spans
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i])
            stack.pop();                                  // L2-L3: O(1) amortized
        left[i] = stack.length ? i - stack[stack.length - 1] : i + 1;  // L4: O(1)
        stack.push(i);                                    // L5: O(1) push
    }

    stack = [];
    for (let i = n - 1; i >= 0; i--) {                   // L6: compute right spans
        while (stack.length && arr[stack[stack.length - 1]] > arr[i])
            stack.pop();                                  // L7-L8: O(1) amortized
        right[i] = stack.length ? stack[stack.length - 1] - i : n - i;  // L9: O(1)
        stack.push(i);                                    // L10: O(1) push
    }

    let total = 0n;
    for (let i = 0; i < n; i++)
        total = (total + BigInt(arr[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;  // L11-L12
    return Number(total);
}

Swift

final class Solution {
    func sumSubarrayMins(_ arr: [Int]) -> Int {
        let modulus = 1_000_000_007
        var stack: [Int] = []
        var total = 0
        for right in 0...arr.count {
            let current = right == arr.count ? Int.min : arr[right]
            while let middle = stack.last, arr[middle] >= current {
                stack.removeLast()
                let left = stack.last ?? -1
                let contribution = ((arr[middle] * (middle - left)) % modulus * (right - middle)) % modulus
                total = (total + contribution) % modulus
            }
            if right < arr.count { stack.append(right) }
        }
        return total
    }
}

Where the time goes, line by line

Variables: n = len(arr).

Line	Per-call cost	Times executed	Contribution
L1-L5 (left span pass)	$O(1)$ amortized	n total pushes/pops	$O(n)$
L6-L10 (right span pass)	$O(1)$ amortized	n total pushes/pops	$O(n)$
L11-L12 (contribution sum)	$O(1)$	n	$O(n)$

Each index is pushed once and popped at most once in each pass. Both passes are $O(n)$.

Complexity

• Time: $O(n)$, two monotonic stack passes plus one summation pass.
• Space: $O(n)$ for left, right, and stack arrays.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Why asymmetric boundaries prevent double counting

Consider arr = [3, 1, 1, 2]. Both arr[1]=1 and arr[2]=1 want to claim arr[0]=3 is to their left.

Using strict left (pop when >=) and non-strict right (pop when >):

• For arr[1]: left goes to boundary (no strictly smaller to left), right stops at arr[2] (equal, not strictly greater). left[1]=2, right[1]=1.
• For arr[2]: left stops at arr[1] (equal, pop on >=). right goes to boundary. left[2]=1, right[2]=2.

Each subarray containing both index 1 and 2 gets counted by exactly one of them. No overlap.

Key takeaways

• Contribution counting flips the problem: instead of “for each subarray find min,” ask “for each element, in how many subarrays is it the min?”
• The left[i] * right[i] formula counts subarrays: pick any of left[i] left boundaries and any of right[i] right boundaries independently.
• Strict vs. non-strict boundary choice (strict left, non-strict right) is the standard fix for equal-element double counting.
• The modulo must be applied at each addition step to avoid integer overflow.

Related topics

• Daily Temperatures, monotonic stack for next-greater
• Largest Rectangle in Histogram, contribution counting with monotonic stack
• Stacks, underlying data structure

Related concepts

• Monotonic Stack, the ordered stack pattern for nearest greater, nearest smaller, and spans.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.