Sum of Subarray Minimums — Monotonic Stack with Contribution

Problem 282 · Sum of Subarray Minimums

Difficulty: Medium · Pattern: Monotonic Stack + Contribution Counting

For each element, find how many subarrays have it as the minimum, multiply by value, sum all.

Intuition

For A[i]: let left[i] = distance to previous strictly smaller element, right[i] = distance to next smaller-or-equal element. Contribution = A[i] * left[i] * right[i].

Solutions

# Python
def sumSubarrayMins(arr):
    MOD = 10**9+7
    n = len(arr)
    # Previous smaller (strict): left[i] = i - prev_smaller_idx
    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)
    # Next smaller or equal: right[i] = next_smaller_idx - i
    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)
    return sum(arr[i]*left[i]*right[i] for i in range(n)) % MOD

// Java
public int sumSubarrayMins(int[] arr) {
    int MOD = 1_000_000_007, n = arr.length;
    int[] left = new int[n], right = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) stack.pop();
        left[i] = i - (stack.isEmpty() ? -1 : stack.peek());
        stack.push(i);
    }
    stack.clear();
    for (int i = n-1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) stack.pop();
        right[i] = (stack.isEmpty() ? n : stack.peek()) - i;
        stack.push(i);
    }
    long ans = 0;
    for (int i = 0; i < n; i++) ans = (ans + (long)arr[i]*left[i]*right[i]) % MOD;
    return (int)ans;
}

Complexity

Time: O(n)
Space: O(n)