Sum of subarray minimums

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Sum of minimums of all subarrays. Monotonic stack to find span for each element as minimum.

Algorithm

1For each element: find left boundary (previous smaller or equal) and right boundary (next smaller). Contribution = arr[i] * left_count * right_count.

Common Pitfalls

•Same as LC 907. Use monotonic stack for O(n). Handle equal elements carefully to avoid double counting.

Sum of subarray minimums.java

Java

// Approach: Monotonic stack (same as above). Sum of arr[i] * (i - left[i]) * (right[i] - i) for each element.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int sumSubMins(int[] arr) {
        int n = arr.length;
        long res = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<Integer> stack = new Stack<>();

        // Previous Less Element
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i])
                stack.pop();

            left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }

        stack.clear();

        // Next Less Element
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])
                stack.pop();

            right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
            stack.push(i);
        }

        for (int i = 0; i < n; i++)
            res += (long) arr[i] * left[i] * right[i];

        return (int) res;
    }
}

Was this solution helpful?