Sum of subarray minimum

Time: O(n)

Space: O(n)

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?