L9: Sum of Subarray Minimums | Stack and Queue Playlist

This chapter explores how to efficiently calculate the Sum of Subarray Minimums using an optimal monotonic stack approach, evolving from an $O(N^2)$ brute-force solution down to an $O(N)$ linear time algorithm by shifting our perspective from generating subarrays to computing individual element contributions.

1. Problem Statement & The Naive Reality

Given an array of integers, your task is to find the minimum of every possible contiguous subarray and sum all those minimums up. Because the final sum can be extremely large, the result must be returned modulo $10^9 + 7$.

Example Array

Array: [3, 1, 2, 4]

Let's list all possible contiguous subarrays starting with each index and observe their minimums:

• Total Sum: $3 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 17$

2. The Naive Brute-Force Approach ($O(N^2)$)

The direct approach is to generate every possible subarray using two nested loops (i and j), tracking the running minimum as j expands, and accumulating the sum.

Naive Code Implementation

public int sumSubarrayMins(int[] arr) {
    int sum = 0;
    int mod = (int) 1e9 + 7;
    int n = arr.length;
    
    for (int i = 0; i < n; i++) {
        int minVal = arr[i];
        for (int j = i; j < n; j++) {
            minVal = Math.min(minVal, arr[j]);
            sum = (sum + minVal) % mod;
        }
    }
    return sum;
}

• Time Complexity: $O(N^2)$ due to nested traversal of all subarrays.
• Space Complexity: $O(1)$ auxiliary space.
• Interviewer Reaction: An $O(N^2)$ solution will fail large constraints ($N \le 3 \times 10^4$). We must optimize it to $O(N)$.

3. Shifting Mental Models: Individual Contributions

Instead of generating every subarray (which is slow), let's ask a different question:

"For any given element in the array, in how many subarrays is it the minimum?"

If we know that an element acts as the minimum in $K$ different subarrays, its total contribution to the final sum is simply:

Revisiting Our Example ([3, 1, 2, 4])

• 3 is the minimum in 1 subarray ([3]) $\rightarrow$ Contribution: $3 \times 1 = 3$

• 1 is the minimum in 6 subarrays $\rightarrow$ Contribution: $1 \times 6 = 6$

• 2 is the minimum in 2 subarrays ([2], [2, 4]) $\rightarrow$ Contribution: $2 \times 2 = 4$

• 4 is the minimum in 1 subarray ([4]) $\rightarrow$ Contribution: $4 \times 1 = 4$

• Total Sum: $3 + 6 + 4 + 4 = 17$

4. Bounding the Range: How Far Can We Stretch?

To find how many subarrays an element $A[i]$ is the minimum in, we need to determine:

1. How far can we go to the left? Find the index of the Previous Smaller Element (PSE). All elements between PSE and $i$ are greater than or equal to $A[i]$, meaning $A[i]$ remains the minimum.
2. How far can we go to the right? Find the index of the Next Smaller Element (NSE). All elements between $i$ and NSE are greater than $A[i]$.

Real-Life Analogy

Think of an element as a person standing on a stage holding an umbrella. How wide is the shade cast by that umbrella? The shade spreads left until it hits someone shorter (who blocks the shade), and spreads right until it hits someone shorter. The total number of sub-umbrellas (subarrays) is the product of the left span and the right span.

Array indices:  0    1    2    3    4    5    6    7
Elements:     [ ...  3    7    8    1    6    4   ... ]
                     ^
                  Index 4 (value = 3)

For element 3 at index 4:

• Left span: The previous smaller element is at index 0. Distance to left = $4 - 0 = 4$ elements.
• Right span: The next smaller element is at index 7 (value 1). Distance to right = $7 - 4 = 3$ elements.
• Total Subarrays: $\text{Left} \times \text{Right} = 4 \times 3 = 12$ subarrays where 3 is the minimum.
• Contribution: $12 \times 3 = 36$.

5. Handling Duplicate Elements & Overcounting

When an array contains duplicate elements (e.g., [1, 1]), relying strictly on "strictly smaller" on both sides will cause the same subarray to be counted twice.

The Solution: Strict vs. Non-Strict Boundaries

To prevent double-counting subarrays with identical elements:

• Next Smaller Element (NSE): Find the first element strictly smaller (<).
• Previous Smaller or Equal Element (PSEE): Find the first element smaller or equal (<=).

By enforcing "smaller" on one side and "smaller-or-equal" on the other, we ensure each subarray is uniquely attributed to exactly one instance of duplicate minimums.

6. Computing NSE and PSEE Using Monotonic Stacks

We use monotonic stacks to compute the indices of the Next Smaller Element and Previous Smaller or Equal Element in linear time $O(N)$.

Finding Next Smaller Element (NSE)

We traverse from right to left (n-1 down to 0), maintaining a monotonic increasing stack of indices.

public int[] findNSE(int[] arr) {
    int n = arr.length;
    int[] nse = new int[n];
    Stack<Integer> st = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && arr[st.peek()] >= arr[i]) {
            st.pop();
        }
        nse[i] = st.isEmpty() ? n : st.peek();
        st.push(i);
    }
    return nse;
}

Finding Previous Smaller or Equal Element (PSEE)

We traverse from left to right (0 up to n-1), maintaining a monotonic increasing stack of indices, popping elements greater than the current element.

public int[] findPSEE(int[] arr) {
    int n = arr.length;
    int[] psee = new int[n];
    Stack<Integer> st = new Stack<>();
    
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && arr[st.peek()] > arr[i]) {
            st.pop();
        }
        psee[i] = st.isEmpty() ? -1 : st.peek();
        st.push(i);
    }
    return psee;
}

7. The Complete Optimal Algorithm

With NSE and PSEE arrays computed, we iterate through each element, calculate its left and right boundaries, and accumulate its contribution modulo $10^9 + 7$.

Master Implementation Code

import java.util.Stack;

public class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int mod = (int) 1e9 + 7;
        
        int[] nse = findNSE(arr);
        int[] psee = findPSEE(arr);
        
        long total = 0;
        
        for (int i = 0; i < n; i++) {
            long left = i - psee[i];
            long right = nse[i] - i;
            
            long contribution = (right * left) % mod;
            contribution = (contribution * arr[i]) % mod;
            
            total = (total + contribution) % mod;
        }
        
        return (int) total;
    }
    
    private int[] findNSE(int[] arr) {
        int n = arr.length;
        int[] nse = new int[n];
        Stack<Integer> st = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[st.peek()] >= arr[i]) {
                st.pop();
            }
            nse[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }
        return nse;
    }
    
    private int[] findPSEE(int[] arr) {
        int n = arr.length;
        int[] psee = new int[n];
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] > arr[i]) {
                st.pop();
            }
            psee[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }
        return psee;
    }
}

8. Complexity Analysis

• Why $O(N)$ time? Each element is pushed and popped from the stack at most once during the NSE and PSEE traversals.
• Why $O(N)$ space? We store the NSE array, PSEE array, and use auxiliary stack memory proportional to array size $N$.

Summary and Key Takeaways

• Shift in Perspective: Transition from generating all $O(N^2)$ subarrays to calculating the individual contribution of each element.
• Contribution Formula: $\text{Contribution} = \text{Element} \times (\text{Elements on Left}) \times (\text{Elements on Right})$.
• Span Calculation: Use Next Smaller Element (NSE) and Previous Smaller or Equal Element (PSEE) indices to find valid left and right boundaries.
• Duplicate Handling: Utilizing "strictly smaller" on one side and "smaller-or-equal" on the other prevents overcounting duplicate values in identical subarrays.
• Monotonic Stack Mastery: Stacks store indices (not values) to enable direct distance arithmetic.
• Integer Overflow Prevention: Use long data types for multiplication steps before applying modulo arithmetic (1e9 + 7).