Sum of subarray minimum

Time: O(n)

Space: O(n)

Problem Overview

For each element, find how many subarrays have it as minimum using monotone stack.

Intuition

For each element, find how many subarrays have it as minimum using monotone stack. Count subarrays where arr[i] is minimum = left_count * right_count.

Algorithm

1For each i: left[i] = distance to previous smaller (or equal) element. right[i] = distance to next smaller element.
2Contribution of arr[i] = arr[i] * left[i] * right[i].

Common Pitfalls

• Handle equal elements: use strictly less on one side to avoid double counting. Result mod 10^9+7.

Sum of subarray minimum.java

Java

// Approach: Monotonic stack. For each element, find left and right boundaries where it is the minimum.
// Contribution = arr[i] * left_count * right_count. Sum all contributions.
// Time: O(n) Space: O(n)
import java.util.Stack;

class Solution {
    public int sumSubMins(int[] arr) {
        final int MOD = 1_000_000_007;
        int n = arr.length;
        int[] prev = new int[n];
        int[] next = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Find Previous Less Element for each index
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i])
                stack.pop();
            
            prev[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        // Find Next Less or Equal Element for each index
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])
                stack.pop();
            
            next[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long sum = 0L;
        for (int i = 0; i < n; i++) {
            long left = i - prev[i];
            long right = next[i] - i;
            sum = (sum + arr[i] * left % MOD * right % MOD) % MOD;
        }
        return (int) sum;
    }
}

Was this solution helpful?