Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sum of Subarray Minimums

MEDIUMProblemSolveExternal Links

Description

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.

Since the answer may be large, return the answer modulo 10^9 + 7.

Examples

Example 1

Input: arr = [3, 1, 2, 4]

Output: 17

Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17.

Example 2

Input: arr = [11, 81, 94, 43, 3]

Output: 444

Explanation: The sum of the minimum values of every contiguous subarray of [11, 81, 94, 43, 3] is 444.

Constraints

  • 1 ≤ arr.length ≤ 3 × 10^4
  • 1 ≤ arr[i] ≤ 3 × 10^4

Editorial

Brute Force

Intuition

The most natural approach is to enumerate every possible subarray, find the minimum of each one, and add all the minimums together.

A subarray is defined by a starting index i and an ending index j (where i ≤ j). There are n × (n + 1) / 2 such pairs for an array of length n. For each pair, we need the minimum element.

We can optimize the inner loop slightly: instead of recomputing the minimum from scratch for each subarray, we maintain a running minimum. When we extend a subarray [i..j] to [i..j+1], the new minimum is just min(old_minimum, arr[j+1]). This avoids an extra loop, reducing the approach from O(n³) to O(n²).

Think of it like sliding a window across the array. You fix the left edge, then gradually widen the window to the right. Each time you widen, you check if the new element is smaller than your current minimum. If it is, the new element becomes the minimum for all further expansions from this start point.

Step-by-Step Explanation

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

Step 1: Starting at i=0:

  • Subarray [3]: min=3. Total += 3 → Total=3.
  • Subarray [3,1]: min=min(3,1)=1. Total += 1 → Total=4.
  • Subarray [3,1,2]: min stays 1 (2 > 1). Total += 1 → Total=5.
  • Subarray [3,1,2,4]: min stays 1 (4 > 1). Total += 1 → Total=6.

Step 2: Starting at i=1:

  • Subarray [1]: min=1. Total=7.
  • Subarray [1,2]: min=1. Total=8.
  • Subarray [1,2,4]: min=1. Total=9.
  • Element 1 is the global minimum, so it dominates all subarrays containing it.

Step 3: Starting at i=2:

  • Subarray [2]: min=2. Total=11.
  • Subarray [2,4]: min=2. Total=13.

Step 4: Starting at i=3:

  • Subarray [4]: min=4. Total=17.

Result: Sum of subarray minimums = 17.

Brute Force — Expanding Subarrays with Running Minimum — Watch how we fix each starting index and expand the subarray rightward, maintaining a running minimum. Notice how smaller elements dominate all further expansions, and how the global minimum (element 1) appears in the most subarrays.

Algorithm

  1. Initialize total = 0
  2. For each starting index i from 0 to n-1:
    • Set min_val = arr[i]
    • For each ending index j from i to n-1:
      • Update min_val = min(min_val, arr[j])
      • Add min_val to total (with modulo)
  3. Return total

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        long long total = 0;
        int MOD = 1e9 + 7;
        
        for (int i = 0; i < n; i++) {
            int min_val = arr[i];
            for (int j = i; j < n; j++) {
                min_val = min(min_val, arr[j]);
                total = (total + min_val) % MOD;
            }
        }
        
        return (int) total;
    }
};
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        n = len(arr)
        MOD = 10**9 + 7
        total = 0
        
        for i in range(n):
            min_val = arr[i]
            for j in range(i, n):
                min_val = min(min_val, arr[j])
                total = (total + min_val) % MOD
        
        return total
class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        long total = 0;
        int MOD = 1_000_000_007;
        
        for (int i = 0; i < n; i++) {
            int minVal = arr[i];
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, arr[j]);
                total = (total + minVal) % MOD;
            }
        }
        
        return (int) total;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each starting index i, the inner loop runs up to n-i times. The total number of iterations is n + (n-1) + ... + 1 = n(n+1)/2, which simplifies to O(n²). Each iteration does O(1) work (one comparison and one addition).

Space Complexity: O(1)

We use only a few integer variables (total, min_val, i, j). No additional data structures are needed beyond the input array.

Why This Approach Is Not Efficient

The brute force visits every subarray individually. With n up to 3 × 10^4, the number of subarrays is n(n+1)/2 ≈ 4.5 × 10^8 — well beyond what can be processed within typical time limits.

The fundamental problem is that we're treating each subarray independently, even though subarrays share structure. When element arr[1]=1 appears as the minimum in 6 different subarrays, the brute force discovers this fact 6 separate times through 6 separate expansions.

Key insight: instead of asking 'what is the minimum of this subarray?', flip the perspective and ask 'for how many subarrays is this element the minimum?' If we can answer this for each element directly, we can compute the total in O(n) without ever enumerating individual subarrays.

A monotonic stack can find the 'reach' of each element — how far left and right it can extend while remaining the minimum — in just two O(n) passes. This transforms the problem from examining all O(n²) subarrays to computing O(n) contributions.

Bar chart comparing O(n²) brute force vs O(n) monotonic stack for n=30,000
Bar chart comparing O(n²) brute force vs O(n) monotonic stack for n=30,000

Optimal Approach - Monotonic Stack with Contribution Counting

Intuition

Instead of finding the minimum of every subarray, we flip the question: for each element arr[i], how many subarrays have arr[i] as their minimum? Then the total sum is simply the sum of arr[i] × count[i] for all i.

For arr[i] to be the minimum of a subarray, that subarray cannot extend past any element smaller than arr[i] on either side. So we need two boundaries for each element:

  • Left boundary (left[i]): the index of the nearest element to the LEFT that is strictly smaller than arr[i]. If none exists, left[i] = -1.
  • Right boundary (right[i]): the index of the nearest element to the RIGHT that is smaller than or equal to arr[i]. If none exists, right[i] = n.

Any subarray where arr[i] is the minimum must:

  • Start at some index between left[i]+1 and i (inclusive) — that gives (i - left[i]) choices.
  • End at some index between i and right[i]-1 (inclusive) — that gives (right[i] - i) choices.

Total subarrays where arr[i] is the minimum = (i - left[i]) × (right[i] - i).

Why the asymmetry (≥ for left, > for right)? When duplicate values exist, we need to assign each subarray to exactly one element. By using ≥ for left boundaries and > for right boundaries, equal elements to the left get popped (the current element 'claims' them), while equal elements to the right don't (they 'claim' those subarrays). This ensures no subarray is double-counted.

A monotonic stack is the perfect tool for finding 'nearest smaller element' — it processes each element exactly once and maintains a naturally ordered set of candidates.

Diagram showing array [3, 1, 2, 4] with each element's contribution as colored rectangles representing subarrays where it is the minimum
Diagram showing array [3, 1, 2, 4] with each element's contribution as colored rectangles representing subarrays where it is the minimum

Step-by-Step Explanation

Let's trace arr = [3, 1, 2, 4] using the contribution technique.

Phase 1: Find left boundaries (nearest smaller to the left).
Process left-to-right with a monotonic stack (pop if ≥):

  • i=0, val=3: Stack empty. left[0] = -1. Push 0.
  • i=1, val=1: Pop 0 (arr[0]=3 ≥ 1). Stack empty. left[1] = -1. Push 1.
  • i=2, val=2: Stack top arr[1]=1 < 2. Don't pop. left[2] = 1. Push 2.
  • i=3, val=4: Stack top arr[2]=2 < 4. Don't pop. left[3] = 2. Push 3.
  • Result: left = [-1, -1, 1, 2]

Phase 2: Find right boundaries (nearest smaller-or-equal to the right).
Process right-to-left with a fresh stack (pop if >):

  • i=3, val=4: Stack empty. right[3] = 4. Push 3.
  • i=2, val=2: Pop 3 (arr[3]=4 > 2). Stack empty. right[2] = 4. Push 2.
  • i=1, val=1: Pop 2 (arr[2]=2 > 1). Stack empty. right[1] = 4. Push 1.
  • i=0, val=3: Stack top arr[1]=1, and 1 is NOT > 3. right[0] = 1. Push 0.
  • Result: right = [1, 4, 4, 4]

Phase 3: Calculate contributions.

  • arr[0]=3: starts (0-(-1))=1, ends (1-0)=1. Subarrays: 1×1=1. Contribution: 3×1 = 3.
  • arr[1]=1: starts (1-(-1))=2, ends (4-1)=3. Subarrays: 2×3=6. Contribution: 1×6 = 6.
  • arr[2]=2: starts (2-1)=1, ends (4-2)=2. Subarrays: 1×2=2. Contribution: 2×2 = 4.
  • arr[3]=4: starts (3-2)=1, ends (4-3)=1. Subarrays: 1×1=1. Contribution: 4×1 = 4.

Result: 3 + 6 + 4 + 4 = 17.

Left Boundary Computation — Monotonic Increasing Stack — Watch how the monotonic stack finds the nearest smaller element to the left for each position. Elements that are greater-or-equal get popped because they cannot form a left boundary. The surviving stack top is the boundary.

Algorithm

  1. Initialize left array with -1 and right array with n
  2. Left boundaries (left-to-right pass):
    • For each index i, pop stack while stack top has arr value ≥ arr[i]
    • If stack is not empty, left[i] = stack top index
    • Push i onto stack
  3. Right boundaries (right-to-left pass with fresh stack):
    • For each index i (from n-1 to 0), pop stack while stack top has arr value > arr[i]
    • If stack is not empty, right[i] = stack top index
    • Push i onto stack
  4. Calculate sum:
    • For each index i, contribution = arr[i] × (i - left[i]) × (right[i] - i)
    • Sum all contributions modulo 10^9 + 7
  5. Return the sum

Code

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

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        const int MOD = 1e9 + 7;
        
        vector<int> left(n, -1), right(n, n);
        stack<int> stk;
        
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && arr[stk.top()] >= arr[i])
                stk.pop();
            if (!stk.empty())
                left[i] = stk.top();
            stk.push(i);
        }
        
        stk = stack<int>();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && arr[stk.top()] > arr[i])
                stk.pop();
            if (!stk.empty())
                right[i] = stk.top();
            stk.push(i);
        }
        
        long long total = 0;
        for (int i = 0; i < n; i++) {
            long long contribution = (long long)(i - left[i]) * (right[i] - i) * arr[i];
            total = (total + contribution) % MOD;
        }
        
        return (int) total;
    }
};
class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        n = len(arr)
        MOD = 10**9 + 7
        
        left = [-1] * n
        right = [n] * n
        
        stack = []
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        stack = []
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        total = sum(
            (i - left[i]) * (right[i] - i) * v
            for i, v in enumerate(arr)
        ) % MOD
        
        return total
import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int MOD = 1_000_000_007;
        
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])
                stack.pop();
            if (!stack.isEmpty())
                left[i] = stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i])
                stack.pop();
            if (!stack.isEmpty())
                right[i] = stack.peek();
            stack.push(i);
        }
        
        long total = 0;
        for (int i = 0; i < n; i++) {
            long contribution = (long)(i - left[i]) * (right[i] - i) * arr[i];
            total = (total + contribution) % MOD;
        }
        
        return (int) total;
    }
}

Complexity Analysis

Time Complexity: O(n)

The algorithm consists of three passes, each taking O(n):

  1. Left boundary computation: each element is pushed and popped from the stack at most once, so total stack operations are O(n).
  2. Right boundary computation: same reasoning, O(n) total stack operations.
  3. Contribution summation: one pass through the array, O(1) work per element.

Overall: O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

We use three auxiliary data structures that scale with input size:

  • The left array of size n: O(n)
  • The right array of size n: O(n)
  • The stack, which can hold at most n elements in the worst case (strictly increasing array): O(n)

Total auxiliary space: O(n).