Sum of Subarray Minimums

medium array dp stack monotonic stack

Problem

Return the sum of min(subarray) over all contiguous subarrays of arr, modulo 10^9 + 7.

Inputarr = [3,1,2,4]

Output17

Each value contributes value × (#subarrays it dominates) — use a monotonic stack.

arr (comma-separated)

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left, right = [0]*n, [0]*n
    st = []
    for i in range(n):
        while st and arr[st[-1]] > arr[i]: st.pop()
        left[i] = i + 1 if not st else i - st[-1]
        st.append(i)
    st.clear()
    for i in range(n - 1, -1, -1):
        while st and arr[st[-1]] >= arr[i]: st.pop()
        right[i] = n - i if not st else st[-1] - i
        st.append(i)
    total = 0
    for i in range(n):
        total = (total + arr[i] * left[i] * right[i]) % MOD
    return total

function sumSubarrayMins(arr) {
  const MOD = 1_000_000_007n;
  const n = arr.length;
  const left = new Array(n).fill(0), right = new Array(n).fill(0);
  const st = [];
  for (let i = 0; i < n; i++) {
    while (st.length && arr[st[st.length - 1]] > arr[i]) st.pop();
    left[i] = st.length ? i - st[st.length - 1] : i + 1;
    st.push(i);
  }
  st.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();
    right[i] = st.length ? st[st.length - 1] - i : n - i;
    st.push(i);
  }
  let total = 0n;
  for (let i = 0; i < n; i++) total = (total + BigInt(arr[i]) * BigInt(left[i]) * BigInt(right[i])) % MOD;
  return Number(total);
}

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

int sumSubarrayMins(vector<int>& arr) {
    const long long MOD = 1000000007LL;
    int n = (int)arr.size();
    vector<int> left(n), right(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] > arr[i]) st.pop();
        left[i] = st.empty() ? i + 1 : i - st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
        right[i] = st.empty() ? n - i : st.top() - i;
        st.push(i);
    }
    long long total = 0;
    for (int i = 0; i < n; i++) total = (total + (long long)arr[i] * left[i] * right[i]) % MOD;
    return (int)total;
}

Explanation

Instead of looking at every subarray (too slow), we flip the question: for each element arr[i], in how many subarrays is it the minimum? If we know that count, the element contributes arr[i] × count to the answer.

An element is the minimum of a subarray when the subarray stretches as far left and right as it can without hitting a smaller element. So we compute left[i] = how many positions to the left it can reach, and right[i] = how many to the right, using two monotonic stack passes.

The total number of subarrays where arr[i] dominates is left[i] × right[i], and the answer is the sum of arr[i] × left[i] × right[i] taken modulo 10^9 + 7. To avoid double-counting ties, one pass uses strict > and the other uses >=.

Example: arr = [3,1,2,4]. The value 1 at index 1 is the minimum reaching across the whole array, giving it a large count, while 4 at the end is only the minimum of the single subarray [4]. Summed up, the total is 17.

Each index is pushed and popped once per pass, so the two passes run in linear time.

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