☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Sum of Subarray Minimums

Medium TUF ID 971 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array arr, consider every contiguous subarray, take its minimum, and add all those minimums together. Because the total can be huge, return it modulo 10^9 + 7.

Constraints (LeetCode 907): 1 ≤ n ≤ 3 × 10^4, 1 ≤ arr[i] ≤ 3 × 10^4. An array of length n has n(n + 1) / 2 subarrays, about 4.5 × 10^8 here, so even listing them one by one is too slow.

Example 1

arr    = [3, 1, 2, 4]
answer = 17
// subarrays: [3] [1] [2] [4] [3,1] [1,2] [2,4] [3,1,2] [1,2,4] [3,1,2,4]
// minimums:   3   1   2   4    1     1     2      1       1        1      → 17

Example 2

arr    = [11, 81, 94, 43, 3]
answer = 444

Example 3

arr    = [2, 2, 2]
answer = 12      // six subarrays, each with minimum 2

Throughout, MOD is the constant 1_000_000_007 declared in the Java file.

Approach 1: Brute force with a running minimum

Intuition. The naive method lists every subarray [i..j] and scans it for the minimum, which is O(n^3). One easy saving: fix the start i and extend the end j one step at a time. The minimum of [i..j] is min(minimum of [i..j-1], arr[j]), so it can be updated in O(1) instead of rescanned.

Algorithm.

  1. For each start i, set min = arr[i].
  2. For each end j from i to n - 1: min = min(min, arr[j]), then add min to the sum, modulo MOD.
  3. Return the sum.
static int bruteForce(int[] arr) {
    long sum = 0;
    for (int i = 0; i < arr.length; i++) {
        int min = arr[i];
        for (int j = i; j < arr.length; j++) {
            min = Math.min(min, arr[j]);
            sum = (sum + min) % MOD;
        }
    }
    return (int) sum;
}

Complexity. Time O(n^2): one constant-time step per subarray. Space O(1).

For n = 3 × 10^4 that is 4.5 × 10^8 steps, which is too slow. Any faster method has to avoid touching subarrays one at a time.

Approach 2: Optimal, the contribution technique

Intuition. Flip the question. Instead of asking “what is the minimum of each subarray?”, ask “for each element, in how many subarrays is it the minimum?” If arr[i] is the minimum of count[i] subarrays, the answer is the sum of arr[i] × count[i].

Element arr[i] is the minimum of a subarray [s..e] exactly when s ≤ i ≤ e and nothing in that range is smaller. Let p be the index of the previous element that is smaller and q the index of the next one. The start can be any of p + 1, ..., i, which gives left[i] = i - p choices, and the end can be any of i, ..., q - 1, which gives right[i] = q - i choices. Starts and ends combine freely, so count[i] = left[i] × right[i]. When there is no smaller element on a side, use p = -1 or q = n.

Both p and q are classic Next Smaller Element lookups, found for all indices in O(n) with a monotonic stack of indices.

The tie rule. With duplicates, a subarray such as [2, 2] has two positions that hold its minimum, and it must be counted once, not twice. The fix is to be strict on one side and non-strict on the other:

Then each subarray is credited to the rightmost position of its minimum, and to no other position. In the code this is just the pop condition: >= in the left-to-right pass leaves a strictly smaller element on top, and > in the right-to-left pass leaves a smaller-or-equal element on top.

Algorithm.

  1. Left-to-right pass with a stack of indices: pop while arr[top] >= arr[i]; then left[i] = i - top, or i + 1 if the stack is empty; push i.
  2. Clear the stack. Right-to-left pass: pop while arr[top] > arr[i]; then right[i] = top - i, or n - i if the stack is empty; push i.
  3. Return the sum of arr[i] × left[i] × right[i], modulo MOD.
static int optimal(int[] arr) {
    int n = arr.length;
    int[] left = new int[n];                     // choices of start: i - (previous strictly smaller index)
    int[] right = new int[n];                    // choices of end: (next smaller-or-equal index) - i
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
        left[i] = st.isEmpty() ? i + 1 : i - st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
        right[i] = st.isEmpty() ? n - i : st.peek() - i;
        st.push(i);
    }
    long sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (sum + (long) arr[i] * left[i] % MOD * right[i]) % MOD;
    }
    return (int) sum;
}

Dry run on [3, 1, 2, 4]:

i arr[i] previous strictly smaller left[i] next smaller or equal right[i] contribution
0 3 none 1 index 1 1 3 × 1 × 1 = 3
1 1 none 2 none 3 1 × 2 × 3 = 6
2 2 index 1 1 none 2 2 × 1 × 2 = 4
3 4 index 2 1 none 1 4 × 1 × 1 = 4

The total is 3 + 6 + 4 + 4 = 17. For instance, the 1 is the minimum of the six subarrays that start at index 0 or 1 and end at index 1, 2 or 3.

On [2, 2, 2] the tie rule gives left = [1, 2, 3] and right = [1, 1, 1], so the total is 2 + 4 + 6 = 12. Making both sides strict would give right = [3, 2, 1] and a total of 20, counting the shared subarrays more than once.

Complexity. Time O(n): each pass pushes and pops every index at most once. Space O(n) for the two count arrays and the stack.

Keeping the arithmetic in range. arr[i] × left[i] × right[i] can approach 3 × 10^4 × 3 × 10^4 × 3 × 10^4 = 2.7 × 10^13, far beyond int. The cast (long) arr[i] makes the whole product long, and reducing modulo MOD after the first multiplication keeps every intermediate value below about 10^9 × n.

Approach 3: One pass, sum of minimums ending at each index

Intuition. A second linear method builds the answer from the left. Let ending[i] be the sum of the minimums of all subarrays that end at i. The final answer is the sum of all ending[i].

Let p be the previous strictly smaller index. Every element strictly between p and i is at least arr[i], so:

So ending[i] = ending[p] + arr[i] × (i - p), with ending[p] taken as 0 when p = -1. The same stack as in Approach 2 delivers p for each i in amortised constant time.

Algorithm.

  1. Scan left to right with a stack of indices. Pop while arr[top] >= arr[i].
  2. p is the top, or -1 if the stack is empty.
  3. ending[i] = (ending[p] or 0) + arr[i] × (i - p), modulo MOD; add it to the sum; push i.
static int endingAtDp(int[] arr) {
    int n = arr.length;
    long[] ending = new long[n];
    Deque<Integer> st = new ArrayDeque<>();
    long sum = 0;
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
        int prev = st.isEmpty() ? -1 : st.peek();
        ending[i] = ((prev >= 0 ? ending[prev] : 0) + (long) arr[i] * (i - prev)) % MOD;
        sum = (sum + ending[i]) % MOD;
        st.push(i);
    }
    return (int) sum;
}

Dry run on [3, 1, 2, 4]: ending = [3, 2, 2 + 2 × 1 = 4, 4 + 4 × 1 = 8], and 3 + 2 + 4 + 8 = 17. Check the last entry by hand: the subarrays ending at index 3 are [4], [2,4], [1,2,4], [3,1,2,4], with minimums 4 + 2 + 1 + 1 = 8.

Complexity. Time O(n) and space O(n), in a single pass instead of two. The contribution view of Approach 2 is the one that generalises best (sum of subarray maximums, subarray ranges), so it is worth knowing both.

Edge cases and pitfalls