Brute Force Approach for Sum of Subarray Minimums

The naive approach involves generating every possible contiguous subarray, finding the minimum element in each, and adding it to a running total.

1. Initialize total_sum = 0.
2. Iterate with a starting pointer i from 0 to n-1.
3. Iterate with an ending pointer j from i to n-1.
4. For each pair (i, j), find the minimum value in arr[i...j].
5. Add this minimum to total_sum.
6. Return total_sum % (10^9 + 7).

python
# Pseudo-code for Brute Force
n = len(arr)
total_sum = 0
for i in range(n):
    current_min = infinity
    for j in range(i, n):
        current_min = min(current_min, arr[j])
        total_sum += current_min

Time Complexity: $O(N^2)$. We have two nested loops. While finding the minimum can be done incrementally in $O(1)$, the total number of operations remains proportional to the number of subarrays, which is $\frac{N(N+1)}{2}$. Why it fails: The constraints state that arr.length can be up to $30,000$. An $O(N^2)$ solution results in approximately $9 \times 10^8$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed in online judges, causing a Time Limit Exceeded (TLE) error.

Core Insight for Sum of Subarray Minimums

The intuition for the optimal solution shifts the perspective from "subarrays" to "elements." Instead of iterating through subarrays and finding the minimum, we fix each element arr[i] and ask: In how many subarrays is arr[i] the minimum value?

If we can determine the range of indices [L, R] where arr[i] remains the minimum, we can calculate its contribution to the total sum using combinatorics.

1. Find the Left Boundary (Previous Less Element): Find the index of the first element to the left of i that is strictly smaller than arr[i]. Let this be prev.
2. Find the Right Boundary (Next Less Element): Find the index of the first element to the right of i that is smaller than arr[i]. Let this be next.
3. The Scope: arr[i] is the minimum for any subarray starting between prev + 1 and i, and ending between i and next - 1.
4. Calculation: The number of such subarrays is (i - prev) * (next - i). The total contribution of arr[i] is arr[i] * (i - prev) * (next - i).

Visual Description: Imagine the array as a bar chart. For a specific bar arr[i], extend a horizontal line to the left until it hits a bar shorter than itself. Do the same to the right. The horizontal distance spanned represents the subarrays where arr[i] is the "valley" or minimum. The monotonic stack allows us to find these "shorter bars" (boundaries) efficiently.

Execution Flow

Let's trace arr = [3, 1, 2, 4].

1. Left Pass (Finding Previous Less Element):

• i=0, val=3: Stack empty. left[0] = 1 (distance to start). Push 0. Stack: [0].
• i=1, val=1: 3 >= 1, pop 0. Stack empty. left[1] = 2 (distance to start). Push 1. Stack: [1].
• i=2, val=2: 1 < 2, no pop. Top is 1. left[2] = 2 - 1 = 1. Push 2. Stack: [1, 2].
• i=3, val=4: 2 < 4, no pop. Top is 2. left[3] = 3 - 2 = 1. Push 3. Stack: [1, 2, 3].
• left array (distances): [1, 2, 1, 1]

2. Right Pass (Finding Next Less Element):

• i=3, val=4: Stack empty. right[3] = 1 (distance to end). Push 3. Stack: [3].
• i=2, val=2: 4 > 2, pop 3. Stack empty. right[2] = 2 (distance to end). Push 2. Stack: [2].
• i=1, val=1: 2 > 1, pop 2. Stack empty. right[1] = 3 (distance to end). Push 1. Stack: [1].
• i=0, val=3: 1 < 3, no pop. Top is 1. right[0] = 1 - 0 = 1. Push 0. Stack: [1, 0].
• right array (distances): [1, 3, 2, 1]

3. Calculation:

• i=0 (3): 3 * 1 * 1 = 3
• i=1 (1): 1 * 2 * 3 = 6
• i=2 (2): 2 * 1 * 2 = 4
• i=3 (4): 4 * 1 * 1 = 4
• Total: 3 + 6 + 4 + 4 = 17.

Proof of Correctness

The algorithm relies on the property that for any subarray, the minimum element is unique (given our duplicate handling rule). By calculating the "span of influence" (i - prev) * (next - i) for each element arr[i], we are counting exactly how many subarrays have arr[i] as their designated minimum.

Summing these contributions covers every possible subarray exactly once. The monotonic stack invariant guarantees that prev and next are correctly identified as the nearest smaller values, ensuring the range is maximal but valid.

Reference Implementation

C++ Solution for LeetCode 907

cpp
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        long long MOD = 1e9 + 7;
        
        vector<int> left(n), right(n);
        stack<int> s;
        
        // Calculate Previous Less Element (PLE) distances
        for (int i = 0; i < n; ++i) {
            // Use >= to handle duplicates strictly on one side
            while (!s.empty() && arr[s.top()] >= arr[i]) {
                s.pop();
            }
            left[i] = s.empty() ? i + 1 : i - s.top();
            s.push(i);
        }
        
        // Clear stack for next pass
        while (!s.empty()) s.pop();
        
        // Calculate Next Less Element (NLE) distances
        for (int i = n - 1; i >= 0; --i) {
            // Use > here (strict inequality)
            while (!s.empty() && arr[s.top()] > arr[i]) {
                s.pop();
            }
            right[i] = s.empty() ? n - i : s.top() - i;
            s.push(i);
        }
        
        long long totalSum = 0;
        for (int i = 0; i < n; ++i) {
            long long contribution = (long long)arr[i] * left[i] * right[i];
            totalSum = (totalSum + contribution) % MOD;
        }
        
        return totalSum;
    }
};

Java Solution for LeetCode 907

java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        long MOD = 1_000_000_007;
        
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        
        // Left Pass
        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();
        
        // Right Pass
        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);
        }
        
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            long contribution = (long) arr[i] * left[i] * right[i];
            totalSum = (totalSum + contribution) % MOD;
        }
        
        return (int) totalSum;
    }
}

Python Solution for LeetCode 907

python
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        n = len(arr)
        MOD = 10**9 + 7
        
        left = [0] * n
        right = [0] * n
        stack = []
        
        # Left Pass
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            left[i] = i + 1 if not stack else i - stack[-1]
            stack.append(i)
            
        stack = [] # Clear stack
        
        # Right Pass
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            right[i] = n - i if not stack else stack[-1] - i
            stack.append(i)
            
        total_sum = 0
        for i in range(n):
            contribution = arr[i] * left[i] * right[i]
            total_sum = (total_sum + contribution) % MOD
            
        return total_sum