Pattern GuideThe Monotonic Stack Pattern
Algorithm Pattern

The Monotonic Stack Pattern

"Remove the useless so you can find the meaningful neighbor."

7 min read Advanced Time: O(N)
01
CORE INTUITION

Selective Memory

⚖️

The Core Intuition

A common algorithmic challenge is needing to quickly find the "next strictly larger" or "next strictly smaller" number for every item in an array. Normally, to find the next larger number for an item, you would have to scan everything to its right using a slow secondary loop, resulting in terrible performance.

The Monotonic Stack pattern solves this by using a standard Stack with one aggressive new rule: the stack must always stay perfectly sorted. "Monotonic" is just a math term that means "entirely non-increasing or entirely non-decreasing".

As we scan through our array one by one, we try to push the current number onto the stack. However, if the new number breaks our strict sorting rule, we ruthlessly delete (pop) the older numbers off the top of the stack until the rule is satisfied again.

Why is this so powerful? Because every time we are forced to delete an older number from the stack, it means we just found its exact matching answer! By kicking out items that are no longer useful, the stack acts as an automated memory system that effortlessly pairs numbers with their next largest or smallest neighbors, reducing a complex nested loop into a lightning-fast single pass.

02
DECREASING STACK

Next Greater Element

Kicks out smaller items — finds Next Greater neighbor

2
0
1
1
2
2
4
3
3
4
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
1
for (let i = 0; i < n; i++) {
2
while (stack.length > 0 && arr[i] > arr[stack.at(-1)]) {
3
const idx = stack.pop();
4
result[idx] = arr[i]; // current is the answer for popped
5
}
6
stack.push(i);
7
}
03
INCREASING STACK

Next Smaller Element

Kicks out larger items — finds Next Smaller neighbor

4
0
5
1
2
2
10
3
8
4
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
1
for (let i = 0; i < n; i++) {
2
while (stack.length > 0 && arr[i] < arr[stack.at(-1)]) {
3
const idx = stack.pop();
4
result[idx] = arr[i]; // current is the answer for popped
5
}
6
stack.push(i);
7
}
04
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
1
for (let i = 0; i < n; i++) {
2
while (stack.length > 0 && arr[i] >= arr[stack.at(-1)]) {
3
stack.pop();
4
}
5
if (stack.length > 0) result[i] = arr[stack.at(-1)];
6
stack.push(i);
7
}

Strategy: Prev Smaller

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

prev_smaller.js
1
for (let i = 0; i < n; i++) {
2
while (stack.length > 0 && arr[i] <= arr[stack.at(-1)]) {
3
stack.pop();
4
}
5
if (stack.length > 0) result[i] = arr[stack.at(-1)];
6
stack.push(i);
7
}
05
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."
06
RULES

The Pop Chain

Every monotonic stack algorithm reduces to one mechanical rule: when a new element breaks the invariant, pop everything it defeats — each pop resolves that element's query. Here is how the chain works.

One Push, One Pop

Every element enters the stack once and leaves at most once. When it leaves via a pop, the current element that forced the pop is its answer. This is what makes the algorithm O(n) — each element is resolved in constant time when evicted.

The Invariant Rule

Before pushing a new element, the stack must be legal — strictly decreasing (for Next Greater) or strictly increasing (for Next Smaller). Evict everything that violates this. Those evicted elements just found their nearest qualifying neighbor.

The Gap Argument

Why is the current element guaranteed to be the nearest greater or smaller? If a closer qualifying element existed between the popped index and the current index, it would have evicted the popped element before the current element could. The invariant guarantees no closer candidate exists.

07
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.
08
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)
09
PRACTICE

Ready to Practice?

Next Greater Element IEasy
Daily TemperaturesMedium
Largest Rectangle in HistogramHard

"Kill the weaker to reveal the meaningful neighbor."