Monotonic Stack | CodeSimulators

CORE INTUITION

Selective Memory

🧍

A line of people, each looking right

Picture people of different heights standing in a line. Each one looks to their right and asks a single question: who is the first person taller than me?

Here is the moment that unlocks everything. Say a short person (height 2) is standing in front of a tall person (height 5). Anyone further down the line who glances back sees the tall one first — the tall person completely blocks the short one from view. So the instant a taller person stands behind a shorter one, that shorter person can never be the answer for anybody to the right. They're hidden. Useless. We can forget them.

That one idea is the monotonic stack. As we walk the line, we keep a stack of only the people still worth remembering — the ones nobody taller has stood behind yet. That stack naturally stays sorted, tallest at the bottom, shortest on top. When a new, taller person arrives, everyone they tower over has just found their answer — "the taller person you were waiting for is me" — and steps out of the stack. (A stack that only ever moves in one direction like that is called monotonic; that's all the word means.)

Walk the line left → right. Keep a "still visible" stack (tallest at bottom):

  heights:  2   1   2   4   3

  see 2  →  stack [2]
  see 1  →  shorter than 2, still visible behind it     stack [2, 1]
  see 2  →  2 > 1, so 1 finally sees someone taller!     pop 1   (1's answer = 2)
            not taller than the 2 below it, so keep       stack [2, 2]
  see 4  →  4 > 2 → pop (answer 4).  4 > 2 → pop (answer 4)     stack [4]
  see 3  →  shorter than 4, still visible                stack [4, 3]

  leftovers 4 and 3 never met anyone taller → their answer is "none" (-1)

Why does this matter so much? The obvious way to answer "next taller on the right" for every person is a double loop: stand on each person, then scan everyone to their right. That's O(N²) — far too slow once the line gets long. The stack turns it into one pass. Each person joins the stack once and leaves once, and the moment they leave, they've found their answer. N pushes, N pops, O(N) total. Trading a nested scan for a single sweep is exactly why this one trick powers Next Greater Element, Daily Temperatures, stock spans, and every histogram and area problem in this set.

DECREASING STACK

Next Greater Element

Kicks out smaller items — finds Next Greater neighbor

STACK STATE (bottom → top)

(empty)

Considering 2 (index 0). Stack is empty — nothing to compare yet.

1 / 15

Decreasing Behavior

The stack stays strictly decreasing (largest at bottom). When a new element is larger than the top, the top's Next Greater is found — pop it and record the answer.

while stack and arr[i] > stack.top(): pop → answer = arr[i]

Strategy: Next Greater

Traverse Left to Right. Pop elements smaller than current — current is their answer.

Also works for:

Stock Span — count consecutive smaller elements
See "Prev Greater" below for the mirror-image query

next_greater.js

for (let i = 0; i < n; i++) {

while (stack.length > 0 && arr[i] > arr[stack.at(-1)]) {

const idx = stack.pop();

result[idx] = arr[i]; // current is the answer for popped

}

stack.push(i);

}

INCREASING STACK

Next Smaller Element

Kicks out larger items — finds Next Smaller neighbor

STACK STATE (bottom → top)

(empty)

Considering 4 (index 0). Stack is empty — nothing to compare yet.

1 / 15

Increasing Behavior

The stack stays strictly increasing (smallest at bottom). When a new element is smaller than the top, the top's Next Smaller is found — pop it and record the answer.

while stack and arr[i] < stack.top(): pop → answer = arr[i]

Strategy: Next Smaller

Traverse Left to Right. Pop elements larger than current — current is their answer.

Also works for:

Histogram — left/right boundaries for each bar
See "Prev Smaller" below for the mirror-image query

next_smaller.js

for (let i = 0; i < n; i++) {

while (stack.length > 0 && arr[i] < arr[stack.at(-1)]) {

const idx = stack.pop();

result[idx] = arr[i]; // current is the answer for popped

}

stack.push(i);

}

MIRROR QUERIES

Previous Greater / Previous Smaller

"Previous Greater/Smaller" doesn't need a separate right-to-left pass — it's solved in the same single left-to-right sweep. The twist: instead of recording the answer for the element being popped, you record it for the element currently being considered, using whatever survives on the stack after popping.

Strategy: Prev Greater

Traverse Left to Right. Pop anything ≥ current off the top; whatever remains is current's previous greater element.

prev_greater.js

for (let i = 0; i < n; i++) {

while (stack.length > 0 && arr[i] >= arr[stack.at(-1)]) {

stack.pop();

}

if (stack.length > 0) result[i] = arr[stack.at(-1)];

stack.push(i);

}

Strategy: Prev Smaller

Traverse Left to Right. Pop anything ≤ current off the top; whatever remains is current's previous smaller element.

prev_smaller.js

for (let i = 0; i < n; i++) {

while (stack.length > 0 && arr[i] <= arr[stack.at(-1)]) {

stack.pop();

}

if (stack.length > 0) result[i] = arr[stack.at(-1)];

stack.push(i);

}

RECOGNITION

Common Clues

"Find the first element on the left/right that is..."
"Nearest greater or smaller neighbor."
"Who is the first neighbor that blocks my view?"
"Find the range or span where this element is the local extrema."
"Look back at past values, but ignore anything that's already hidden."
"Histogram Related Problems: left and right boundaries for each bar."

RULES

The Pop Chain

Every monotonic-stack problem comes down to one rule: when a taller (or shorter) newcomer arrives, pop everyone it beats — and each pop is one person getting their answer. Here is why that chain is both fast and correct.

One Push, One Pop

Every person joins the stack once and leaves at most once. Whoever forces them out is their answer. That's just two moves per person across the whole walk — which is what makes it O(N), not the O(N²) of a nested scan.

The Invariant Rule

Before a newcomer joins, the stack has to stay sorted — decreasing for Next Greater, increasing for Next Smaller. Anyone who breaks that order gets popped, and every popped person has just found their nearest taller (or smaller) neighbor.

The Gap Argument

Why is the newcomer guaranteed to be the nearest answer, not just some answer? If a closer taller person existed in between, that person would have popped our element earlier — before the newcomer ever arrived. Since our element was still waiting on the stack, no closer answer exists.

PITFALLS

Common Pitfalls

Using `if` instead of `while`

A new strong element might kill multiple past elements. Using an if statement will only evaluate the very top. Always use a loop!

Storing Values instead of Indices

Storing indices is mandatory for calculating Width, Range, or Area (like in Histograms). When in doubt, store indices.

Forgetting the Leftovers

Whatever's still on the stack after the loop ends never got popped, so it never got an answer. Default those to -1 (or whatever "no answer" means for the problem) — don't leave them uninitialized.

Circular Arrays

"Next greater, and the array wraps around" (e.g. Next Greater Element II) needs indices 0 to 2N-1, using i % N to read values — this lets an element "see" past the physical end without actually duplicating the array.

Will I encounter equal elements? Use >= in the pop condition and equal elements get popped — you find the nearest strictly greater element. Use > and equal elements stay on the stack, so a run of duplicates resolves to each other first. Neither is "more correct" — pick whichever the problem statement actually asks for.

RECAP

Final Checklist

1. What is my current element killing?
2. Do I need next or previous?
3. Increasing or decreasing?
4. Will I encounter equal elements? (>= vs > — see Ch.07)

PRACTICE

Ready to Practice?

Next Greater Element IEasy

Daily TemperaturesMedium

Largest Rectangle in HistogramHard

"Kill the weaker to reveal the meaningful neighbor."

Selective Memory

A line of people, each looking right

Next Greater Element

Kicks out smaller items — finds Next Greater neighbor

Strategy: Next Greater

Also works for:

Next Smaller Element

Kicks out larger items — finds Next Smaller neighbor

Strategy: Next Smaller

Also works for:

Previous Greater / Previous Smaller

Strategy: Prev Greater

Strategy: Prev Smaller

Common Clues

The Pop Chain

One Push, One Pop

The Invariant Rule

The Gap Argument

Common Pitfalls

Using if instead of while

Storing Values instead of Indices

Forgetting the Leftovers

Circular Arrays

Final Checklist

Ready to Practice?

Using `if` instead of `while`