Skip to content

level 8 · Core techniques

Monotonic Stack

A stack kept in order — so one new value can answer many old questions at once.

11 min 95 XP

what is it

Start here

Here's the problem: for every value in a list, find the next value to its right that is bigger than it. The obvious solution is to look right from each one until you find something bigger — and that's O(n²).

A monotonic stack does it in a single pass. The idea: keep a stack of the positions whose answer you don't know yet — and keep that stack in decreasing order.

Now watch what happens when a new value arrives. Everything on the stack that's smaller than it has, at that exact instant, found its answer. Not one of them — *all* of them, popped off together. The new value answers a whole backlog in one go.

In the visualization the pink cells are what's on the stack: the positions still waiting. Notice they always read largest-to-smallest, left to right. That ordering is the invariant, and it's why a single arrival can settle many at once — if the stack weren't sorted, you'd have to search it.

Every index is pushed exactly once and popped at most once. Two operations per element, total. That's O(n) — and it's how the terrifying 'Largest Rectangle in Histogram' and 'Trapping Rain Water' both become tractable.

real-life analogy

Picture it

A queue of people waiting to see someone taller

People stand in a line, each waiting to spot someone taller than themselves. They naturally stand so the tallest is at the back of the waiting group. When a very tall person walks past, everyone shorter than them — several people at once — gets their answer and leaves. The tall ones keep waiting.

interactive visualization

Watch it run

Pink = still on the stack, waiting for an answer. Green = answered.

  1. 4
    0
  2. 9
    1
  3. 3
    2
  4. 6
    3
  5. 2
    4
  6. 8
    5
  7. 1
    6
  8. 7
    7

For every value, find the next value to its right that is bigger. The obvious way compares every pair — O(n²). A monotonic stack does it in one pass.

step 01/23

  • comparing
  • in final place
  • found it
1// For each value, find the next value to its right that is bigger.
2function nextGreater(a) {
3 const result = new Array(a.length).fill(-1);
4 const stack = []; // holds INDEXES, kept decreasing
5
6 for (let i = 0; i < a.length; i++) {
7 // Anything smaller than a[i] has just found its answer.
8 while (stack.length && a[stack[stack.length - 1]] < a[i]) {
9 const j = stack.pop();
10 result[j] = a[i];
11 }
12 stack.push(i);
13 }
14
15 return result; // whatever is left never found a bigger value
16}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

23 steps

complexity

What it costs

best case
O(n)
average
O(n)
worst case
O(n)
extra memory
O(n)

Each index is pushed once and popped at most once — two operations per element no matter how the inner while-loop looks. That's O(n), down from the O(n²) of checking every pair. The stack itself can hold up to n items.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Seeing the nested while-loop and assuming it's O(n²).

    It isn't. The inner loop can only pop what was pushed, and each index is pushed once. Total work across the whole run is bounded by 2n — this is amortised analysis in action.

  • Storing values on the stack instead of indexes.

    Store indexes. You almost always need to know *where* the waiting element was — to write into a results array, or to compute a width. Values alone throw that away.

  • Breaking the monotonic invariant.

    If the stack isn't kept in order, you can't pop 'everything smaller' in one sweep — you'd have to search it, and the O(n) collapses. The ordering is the whole algorithm.

  • Forgetting the leftovers.

    Whatever is still on the stack at the end never found anything bigger. Those get −1 (or whatever your 'none' value is) — don't just drop them.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+95 XP

01What does the stack actually hold?

02There's a while-loop inside a for-loop. Why isn't it O(n²)?

03A new, larger value arrives. What happens to the stack?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.