Skip to content

From Chains to Stacks

The Problem That Makes You Need This

Given an array A of non-negative integers, compute the sum of minimums over all subarrays:

sum of min(A[l..r])   for all 0 <= l <= r < n

For A = [3, 1, 2, 1], the answer is 13. We will derive this together and verify at the end.

The brute-force approach iterates over all O(N²) pairs (l, r) and tracks the running minimum — O(N³) naively, O(N²) with the rolling minimum trick. For N = 30,000 that's 900 million operations. Too slow.

There's an O(N) solution. It doesn't iterate over pairs at all. Instead, it asks a completely different question.

The Contribution Insight: Fix the Element, Not the Boundaries

Instead of asking "what is the minimum of this subarray?", ask:

For each element A[i], how many subarrays have A[i] as their minimum?

If we can answer this for every i, the total sum is just:

ans = sum over i of  A[i] * (number of subarrays where A[i] is the minimum)

This reframing is powerful. Let's figure out what "subarrays where A[i] is the minimum" looks like geometrically.

A[i] is the minimum of subarray [l..r] exactly when: - l <= i <= r (the subarray contains position i) - No element in [l..r] is strictly smaller than A[i]

So the left boundary l can extend leftward from i as long as it doesn't cross any element smaller than A[i]. The right boundary r can extend rightward similarly.

Define: - L[i] = the nearest index to the LEFT with A[L[i]] < A[i]. This is the hard left wall — the subarray cannot include L[i] or further left. - R[i] = the nearest index to the RIGHT with A[R[i]] < A[i]. This is the hard right wall.

With sentinels: if no such index exists, set L[i] = -1 and R[i] = n.

The number of valid (l, r) pairs is exactly (i - L[i]) × (R[i] - i): - l can be any of L[i]+1, L[i]+2, ..., i — that's i - L[i] choices - r can be any of i, i+1, ..., R[i]-1 — that's R[i] - i choices

Contribution of A[i]  =  A[i]  ×  (i − L[i])  ×  (R[i] − i)

This is the contribution formula. Everything else in this lesson is about computing L and R correctly and efficiently.

The Duplicate Trap

Here's where almost every first implementation breaks.

Consider A = [3, 1, 2, 1]. There are two 1s, at positions 1 and 3. Both are the global minimum. Any subarray containing both of them has minimum 1.

Take the subarray [3, 1, 2, 1] — the full array. Who gets to "claim" this subarray? If both i=1 and i=3 count it, you double-count.

What breaks if you use strict < on BOTH sides:

For i=1 (first 1): - L[1]: previous element strictly less than 1 → none → L[1] = -1 - R[1]: next element strictly less than 1 → none → R[1] = 4 - Contribution = 1 × (1−(−1)) × (4−1) = 1 × 2 × 3 = 6

For i=3 (second 1): - L[3]: previous element strictly less than 1 → none → L[3] = -1 - R[3]: next element strictly less than 1 → none → R[3] = 4 - Contribution = 1 × (3−(−1)) × (4−3) = 1 × 4 × 1 = 4

Total contribution from the two 1s = 6 + 4 = 10. But there are only 7 subarrays that contain a 1 (every subarray that isn't just [3] or [2]). We counted too many.

The full array [3,1,2,1] got claimed by BOTH i=1 (it's in its right range) and i=3 (it's in its left range). That's the double count.

The fix: use different strictness on each side.

Use strict < on the LEFT, and <= (less-or-equal) on the RIGHT: - L[i] = nearest index to the left where A[j] < A[i] (strictly less) - R[i] = nearest index to the right where A[j] <= A[i] (less OR equal)

Now revisit A = [3, 1, 2, 1]:

For i=1 (first 1): - L[1] = -1 (nothing strictly less to the left) - R[1] = 3 (next element ≤ 1 is at index 3, since A[3]=1 ≤ 1) - Contribution = 1 × (1−(−1)) × (3−1) = 1 × 2 × 2 = 4 - Claims subarrays: l∈{0,1}, r∈{1,2} → [3,1], [1], [3,1,2], [1,2]

For i=3 (second 1): - L[3] = -1 (no element strictly less; A[1]=1 is equal, not strictly less) - R[3] = 4 (nothing to the right) - Contribution = 1 × (3−(−1)) × (4−3) = 1 × 4 × 1 = 4 - Claims subarrays: l∈{0,1,2,3}, r∈{3} → [3,1,2,1], [1,2,1], [2,1], [1]

No subarray is claimed by both. Every subarray that ends before index 3 is claimed by i=1. Every subarray that ends AT index 3 is claimed by i=3. The equal element on the right (R[1]=3) cuts the first 1 off, handing ownership of the right half to the second 1.

The rule: When two equal elements might compete for the same subarray, make the rightmost one "win" by having the leftmost one's right boundary stop at the next equal element. Strict < on left, <= on right achieves exactly this.

Alternatively, you can use <= on the left and strict < on the right — the leftmost element wins. Either convention is fine; the critical thing is that the two sides use different strictness.

Why a Stack? Because Chains Are LIFO

Now we know what to compute. How do we compute all L[i] and all R[i] in O(N)?

Think about what L[i] means: the nearest element to the left that is strictly smaller. As you scan left-to-right, you're maintaining a set of candidates — elements that might still be the answer for some future i.

When can you discard a candidate? If the current element A[i] is smaller than or equal to some candidate A[j] (where j < i), then A[j] can never be L[k] for any k > i. Why? Because A[i] is both closer to k and not larger — any future element needing a "previous strictly-less" answer would find A[i] before A[j].

So you maintain a stack of candidates (by index). When you see A[i]: 1. Pop off all candidates that are >= A[i] — they're eclipsed by A[i]. 2. The new top of the stack (if any) is L[i] — it's the nearest remaining element that's strictly less. 3. Push i onto the stack as a new candidate.

Which candidates get eclipsed when a new element arrives? The most recently added ones — the top of the stack. An older, smaller element deeper in the stack is safe: it's already survived every challenge.

New element eclipses recent candidates from the top down. That's last-in, first-out. That's a stack.

Here's the chain picture: the stack at any point holds indices whose values form an increasing sequence from bottom to top (for L[i] left pass). A new element pops everything at the top that is >= it, breaking the chain from the top inward.

Decreasing chain shown as a staircase over histogram bars

Tracing the Left Pass on [3, 1, 2, 1]

We build L by scanning left to right, popping while A[top] >= A[i]:

i A[i] Stack (indices, values) Pop condition L[i] Stack after
0 3 [] — -1 [0 → 3]
1 1 [0→3] 3 ≥ 1, pop 0 -1 [1 → 1]
2 2 [1→1] 1 < 2, stop 1 [1→1, 2→2]
3 1 [1→1, 2→2] 2 ≥ 1, pop 2. 1 ≥ 1, pop 1. -1 [3 → 1]

Result: L = [-1, -1, 1, -1]

Reading this: L[2] = 1 means A[1]=1 is the nearest element to the left that is strictly less than A[2]=2. L[0]=L[1]=L[3]=-1 means there's nothing smaller to their left.

Tracing the Right Pass on [3, 1, 2, 1]

We build R by scanning right to left, popping while A[top] > A[i]:

i A[i] Stack (indices, values) Pop condition R[i] Stack after
3 1 [] — 4 (n) [3 → 1]
2 2 [3→1] 1 ≤ 2, stop 3 [3→1, 2→2]
1 1 [3→1, 2→2] 2 > 1, pop 2. 1 ≤ 1, stop. 3 [3→1, 1→1]
0 3 [3→1, 1→1] 1 ≤ 3, stop 1 [3→1, 1→1, 0→3]

Result: R = [1, 3, 3, 4]

Reading this: R[1] = 3 means A[3]=1 is the nearest element to the right that is ≤ A[1]=1. R[0] = 1 means A[1]=1 is the nearest element to the right that is ≤ A[0]=3.

Putting It Together

With L = [-1, -1, 1, -1] and R = [1, 3, 3, 4]:

i A[i] i − L[i] R[i] − i Contribution
0 3 1 1 3 × 1 × 1 = 3
1 1 2 2 1 × 2 × 2 = 4
2 2 1 1 2 × 1 × 1 = 2
3 1 4 1 1 × 4 × 1 = 4

Total = 13.

Verify manually — all subarrays of [3, 1, 2, 1]:

Length 1:  [3]=3,  [1]=1,  [2]=2,  [1]=1      → sum = 7
Length 2:  [3,1]=1, [1,2]=1, [2,1]=1           → sum = 3
Length 3:  [3,1,2]=1, [1,2,1]=1                → sum = 2
Length 4:  [3,1,2,1]=1                          → sum = 1
                                                 Total = 13  ✓

The Two Phases of Each Element

At every step in the left pass, each element goes through exactly two phases:

  • Push = join the candidate chain. The element fits the increasing order (bottom to top), so it becomes a new candidate for future queries.
  • Pop = chain disturbed. A newer, smaller element arrives. The top candidates are larger (or equal), so they're eclipsed — they'll never be a L[i] answer for any future i. At the moment of popping, they lose relevance.

Extend vs Disturb — push when smaller, pop when larger

NGE algorithm step-by-step trace on array [4, 5, 2, 10, 8]

The O(N) Argument

There's a while loop inside a for loop. Shouldn't this be O(N²)?

No. Here's the precise argument:

Each of the N elements is pushed onto the stack exactly once. Each element is popped from the stack at most once. So the total number of stack operations across the entire loop is at most 2N.

The while loop doesn't run N times per outer iteration. It might run 0 times on one step and 5 times on the next — but across all N steps combined, the total pops can't exceed N (because there were only N pushes).

Total operations: N pushes + at most N pops = 2N. That's O(N).

Think of it this way: every element has a birth (push) and a death (pop). Every element is born exactly once and dies at most once. The total life events are bounded by 2N, regardless of the input.

The Code

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> L(n, -1), R(n, n);
    stack<int> st;

    // Left pass: L[i] = previous index with a[j] < a[i]
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i])
            st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // Right pass: R[i] = next index with a[j] <= a[i]
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] > a[i])
            st.pop();
        R[i] = st.empty() ? n : st.top();
        st.push(i);
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = (ans + (long long)(a[i] % MOD) * ((i - L[i]) % MOD) % MOD * ((R[i] - i) % MOD)) % MOD;
    }
    cout << ans << "\n";

    return 0;
}

A few things to notice:

  • Left pass pops >=, right pass pops > — this is the asymmetric strictness that prevents duplicate elements from double-counting.
  • We push indices, not values. The comparison uses a[st.top()] to get the value, but the stack holds i so we can compute distances.
  • Two separate passes. You could combine them into a single forward pass that simultaneously pops right-boundary answers when elements are popped. But two passes is clearer and easier to get right.

Chain Breaking as a General Pattern

The monotonic stack is really a mechanism for detecting chain breakpoints — moments where an ordering relationship that held for a sequence of elements suddenly fails.

In the subarray minimum problem: - The chain is: elements in the stack are increasing (candidates for "I'm the previous smaller element") - A chain break happens when a new element is smaller than the top — the top element's "dominance range" just ended

This same logic — maintain an ordered chain, pop when the chain breaks, the breaking element records who it broke — appears in many forms across the remaining chapters. The geometry changes (intervals, slopes, rectangles), but the chain-breaking mechanism is identical.

When you see a monotonic stack problem in the wild, ask: what is the chain? and what does a chain break mean semantically? The code follows from that.

Try It

The starter code has the structure ready. Your task: fill in the two TODO lines (the pop conditions) and see the sum of subarray minimums computed correctly.

Input format: Line 1: n Line 2: n space-separated integers

Example input: 

4
3 1 2 1
Expected output: 13

More test cases to verify your understanding:

All equal: 

4
2 2 2 2
Expected: 20 — each of the 10 subarrays has minimum 2. With strict left and non-strict right, only the rightmost 2 in each run claims subarrays that span equal elements. Verify the contributions: i=0 gets 1 subarray, i=1 gets 2, i=2 gets 3, i=3 gets 4. Contributions: 2+4+6+8=20.

Sorted ascending: 

4
1 2 3 4
Expected: 20 — the minimum of every subarray is its leftmost element. Subarray [l..r] has minimum A[l]=l+1. Sum = Σ A[l] × (n - l) = 1×4 + 2×3 + 3×2 + 4×1 = 4+6+6+4=20.

Sorted descending: 

4
4 3 2 1
Expected: 20 — mirror of the above. Every minimum is the rightmost element. Same sum.

Try predicting the boundary arrays L and R before running, then trace through the code to see where the contribution formula gets each case right.