2Brute2Best
🔥0

Monotonic Stack Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Keep a stack that is always sorted. When a new element breaks the order, the popped elements just found their "next greater/smaller".

5 sub-patterns · 19 questions

Remember this · Monotonic Stack
Trigger
Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"
Think
When a new element arrives, which older elements can never be the answer again?
Key question
Is my stack increasing or decreasing, and what do I record when I pop?
A

What is this pattern?

A monotonic stack is a stack whose values are always sorted — always decreasing from bottom to top, or always increasing. When a new element would break that order, you pop until the order is fixed again.

The trick is what those pops mean. Say the stack is decreasing and x arrives. Every element popped is smaller than x and has been waiting for something bigger — so x is its next greater element. And after the pops, whatever is left on top is the nearest earlier element that is at least x — the previous greater of x, for free.

So one left-to-right pass answers "for each element, who is the first bigger (or smaller) one to the right / left?" Every element is pushed once and popped at most once: O(N) instead of the O(N²) "scan right from every index".

People of different heights stand in a line, all looking to the right, each waiting to see the first person taller than them. When a tall person walks in at the end, every shorter person still waiting gets their answer at once and stops waiting. The people still waiting are always in decreasing height order — if a short person stood after a taller one, the taller one would be hiding nobody, and the short one would already have been answered by whoever came next.

B

See it move

Next greater element. The stack tracks are one stack of indices (values below them), bottom on the left; the values decrease bottom → top. Purple = an answer just written when its index was popped. Orange = leftovers that get -1.

A bigger arrival answers everyone smallernums = [2, 7, 3, 1, 5, 4, 8, 6]step 1/16
nums
0
1
2
3
4
5
6
7
2
7
3
1
5
4
8
6
ans
0
1
2
3
4
5
6
7
?
?
?
?
?
?
?
?
stack.idx
stack.val
State
stack size
0
Nothing is waiting yet

Go left to right. The stack holds indices still waiting for something bigger. Their values always decrease from bottom to top.

Largest Rectangle in Histogram. The stack keeps bar indices with increasing heights. When a bar is popped, the bar arriving now is its right wall and the new top is its left wall. The last cell is a fake bar of height 0 that flushes the stack.

A popped bar knows both of its wallsheights = [2, 1, 5, 6, 2, 3]step 1/14
heights
0
1
2
3
4
5
6
2
1
5
6
2
3
0
stack.idx
stack.val
State
best
0
Increasing stack of bar indices

A bar's rectangle stretches left and right until a shorter bar blocks it. We add a fake bar of height 0 at the end so every real bar gets popped.

C

How do I recognise it?

  • "Next greater", "next smaller", "previous greater", "nearest bigger to the left" — any "first element to the right/left that beats me".

  • "How many days until…" a warmer day, a higher price (distance to the next greater).

  • "How many consecutive previous days were ≤ today?" (stock span — distance to the previous greater).

  • "For each element, how far does it stretch as the minimum / maximum?" — largest rectangle in a histogram, sum of subarray minimums, sum of ranges.

  • "Remove k digits / letters to make the smallest result" — a smaller later element should kick out bigger earlier ones.

  • dp[i] needs the best of the last k dp values — a monotonic deque.

  • The brute force is "for each i, scan right (or left) until something bigger shows up" — O(N²).

Looks like Monotonic Stack, but isn't

Valid parentheses, asteroid collision, evaluate an expression
→ Stack

You pop because something was matched or collided, not because the new value is bigger or smaller. The stack isn't kept sorted.

Maximum of every window of size k
→ Sliding Window (monotonic deque)

Same sorted-container idea, but the window's left edge moves, so old indices also expire from the front. That's a deque inside a sliding window. Here, the deque version is used for DP over the last k states.

"The smallest element greater than x" (closest by value, anywhere in the array)
→ Sorting / Binary Search / an ordered set

"Next greater" in this pattern means first by position to the right, not closest by value. If position doesn't matter, sort and binary search (or use set::upper_bound).

Trapping Rain Water
→ Two Pointers (simplest)

A monotonic stack solves it too (pop a bar when a taller wall arrives and fill the water above it), but two pointers does it in O(1) extra space.

"Top k largest" or "k-th largest"
→ Heap

You need the order of many values, not each element's nearest bigger neighbour.

D

How would I discover it from scratch?

Don't memorise “use monotonic stack”. Ask these questions in order — the pattern falls out.

For every index i, walk right until you find something bigger. Worst case (a decreasing array) every walk goes to the end: O(N²).

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Next / previous greater

4 questions

Decreasing stack. A bigger arrival pops every smaller waiting element and becomes their next greater. Whatever never gets popped has no answer.

02

Next / previous smaller

4 questions

Increasing stack. A smaller arrival pops every bigger waiting element. The same shape powers greedy "make it as small as possible" questions, where the stack is the answer being built.

03

Contribution / boundaries

5 questions

For each element, find how far it stretches left and right while staying the minimum (or maximum): its previous smaller and next smaller. Then each element's contribution can be counted directly instead of looking at every subarray.

04

Span / dominance

3 questions

"How many consecutive earlier items are ≤ me?" is the distance to the previous greater. Pop everything ≤ the new value; the top is the wall that stops the span.

05

Monotonic deque for DP

3 questions

When dp[i] depends on the best dp value among the last k states, keep those candidates in a monotonic deque: the front is the best, the back loses to newer, better states.

F

Don't mix these up

Increasing stack vs Decreasing stack

Name what you're looking for. Next/previous greater → keep a decreasing stack (a bigger arrival pops the smaller ones). Next/previous smaller → keep an increasing stack.

Next greater (Daily Temperatures) vs Previous greater (Stock Span)

Same decreasing stack, same pass. Next greater is written for the element being popped (the arrival answers it). Previous greater is read from the top after popping (it answers the arrival).

Monotonic Stack vs Stack

Pop because the new value is bigger/smaller than the top → monotonic stack. Pop because something was matched or collided → plain stack.

Monotonic stack vs Monotonic deque

A stack only changes at one end. Use a deque when old indices must also leave from the front because they fell out of a window of size k.

Largest Rectangle in Histogram (LC 84) vs Sum of Subarray Minimums (LC 907)

Both need previous and next smaller. LC 84 takes a max over bars, so equal heights are harmless. LC 907 sums over subarrays, so equal values must be counted once: strict on one side, ≤ on the other.

G

Code templates (C++)

Next greater element (resolve on pop)

Decreasing stack of indices. The answer is written when an index is popped. For next smaller, flip < to >. For a circular array, loop i from 0 to 2n − 1, use i % n, and push only when i < n.

next-greater-template.cpp
// Next greater element to the right; -1 if none. Decreasing stack of indices.
vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);                          // leftovers keep -1
    stack<int> st;                                   // indices; values decrease bottom → top
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {  // a[i] beats the waiting top
            ans[st.top()] = a[i];                    // answer written on POP
            st.pop();
        }
        st.push(i);                                  // a[i] now waits for its own answer
    }
    return ans;
}

Previous greater element (read the top)

Pop everything that can never stop anyone again (here: everything ≤ a[i], because a[i] is in front of them and at least as tall). Then the top is a[i]'s previous greater — or none if the stack is empty. Flip the comparison for previous smaller; run right-to-left to get next greater/smaller this way instead.

previous-greater-template.cpp
// Stock span: how many consecutive days up to today had price <= today's.
// = distance to the previous strictly greater price. Decreasing stack of indices.
vector<int> stockSpan(vector<int>& price) {
    int n = price.size();
    vector<int> span(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && price[st.top()] <= price[i])  // can never block anyone again
            st.pop();
        int prevGreater = st.empty() ? -1 : st.top();  // answer = top AFTER popping
        span[i] = i - prevGreater;
        st.push(i);
    }
    return span;
}

Boundaries and contribution

For each element, how far does it stay the minimum? left[i] = previous strictly smaller, right[i] = next smaller-or-equal, so equal values are counted once. Then it is the minimum of (i − left) × (right − i) subarrays. Largest Rectangle uses the same two arrays: width = right − left − 1.

contribution-template.cpp
// Sum of min(subarray) over all subarrays: each a[i] counts as the minimum
// of (i - left[i]) * (right[i] - i) subarrays.
long long sumOfSubarrayMins(vector<int>& a) {
    int n = a.size();
    vector<int> left(n), right(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {                    // previous STRICTLY smaller
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    st = stack<int>();
    for (int i = n - 1; i >= 0; i--) {               // next smaller OR EQUAL
        while (!st.empty() && a[st.top()] > a[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long total = 0;
    for (int i = 0; i < n; i++)
        total += (long long)a[i] * (i - left[i]) * (right[i] - i);
    return total;                                    // (LC 907 also wants % 1e9+7)
}

Monotonic deque for DP

dp[i] needs the max of the last k dp values. The deque holds indices with decreasing dp. Drop the front when it falls out of the window (< i − k), read the front, then drop dominated indices from the back before pushing i. O(N) instead of O(N·k).

deque-dp-template.cpp
// Jump Game VI: dp[i] = nums[i] + max(dp[i-k .. i-1]). Deque of indices, dp decreasing.
int maxResult(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long long> dp(n);
    deque<int> dq;
    dp[0] = nums[0];
    dq.push_back(0);
    for (int i = 1; i < n; i++) {
        if (dq.front() < i - k) dq.pop_front();      // left the window (one per step)
        dp[i] = nums[i] + dp[dq.front()];            // front = best of the last k
        while (!dq.empty() && dp[dq.back()] <= dp[i])
            dq.pop_back();                           // older AND not better: never needed
        dq.push_back(i);
    }
    return dp[n - 1];
}
Next
Start with Next / previous greater