Sum of Subarray Minimums

Problem

Given an integer array, return the sum, modulo 10⁹+7, of the minimum value across every contiguous subarray.

Constraints

• 1 ≤ n ≤ 3·10⁴
• 1 ≤ arr[i] ≤ 3·10⁴

Approach — Monotonic Stack

This is a Monotonic Stack problem. The idea: scan once and keep a stack whose order stays meaningful, popping elements as soon as a later value resolves them. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10**9 + 7
        n = len(arr)
        st = []
        total = 0
        for i in range(n + 1):
            cur = arr[i] if i < n else float('-inf')
            while st and arr[st[-1]] >= cur:
                j = st.pop()
                left = st[-1] if st else -1
                total += arr[j] * (j - left) * (i - j)
            st.append(i)
        return total % MOD

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.