How does the monotonic stack solve next greater element in O(n)?

Scan left to right keeping a stack of indices whose values decrease downward. Each new element pops every smaller value off the top — and each popped element has just found its next greater element (the current one). Then the new element is pushed. Every element is pushed once and popped at most once, so the total work is O(n) even though there is an inner loop.

Why is the monotonic stack O(n) despite having a nested loop?

The inner while-loop can pop many elements in one step, which looks like it could be O(n squared). But each element enters the stack exactly once and leaves exactly once across the entire run, so the total number of pops over all iterations is at most n. This amortized argument gives O(n) overall.

What problems does a monotonic stack solve?

Next greater element, previous greater or smaller element, daily temperatures (days until a warmer day), largest rectangle in a histogram, trapping rain water, stock span, and removing digits to form the smallest number. Whenever a problem asks about the nearest larger or smaller neighbor, a monotonic stack is usually the linear-time answer.

Algorithms · Next Greater Element

The Monotonic Stack.

Q: What is a monotonic stack?

A monotonic stack is a stack whose elements are kept in sorted order — always increasing or always decreasing from bottom to top. You maintain that order by popping elements that would break it before pushing a new one. It turns a whole family of 'find the next/previous greater or smaller element' problems into a single linear pass.

For every bar in a row, which is the next taller one to its right? The brute-force answer looks right at every pair — O(n²). The elegant answer keeps a single stack that only ever decreases, so the moment a taller bar arrives it resolves everything shorter waiting below it. One pass, and a whole family of problems falls.

O(n) time · O(n) space · stack · arrays

next greater

For each element, the first element to its right that is strictly larger — or none.

monotonic

A stack kept in sorted order. Here: values decrease from bottom to top.

the pop

A new taller bar pops every shorter bar off the stack — each just found its answer.

amortized O(n)

Each bar is pushed once and popped once, so total work is linear despite the inner loop.

next_greater.js — a stack that only decreases

Ready

A row of bars. We want each bar's next greater element — the first taller bar to its right. Press Step to walk the pointer, keeping a stack of bars still waiting for their answer.

–

pointer i

stack size

resolved

push+pop ops

How it works

The insight is that a bar can’t know its next-greater neighbor until that neighbor appears. So we keep every bar still waiting for an answer on a stack — and because any bar taller than one already waiting would have resolved it, the waiting bars are always in decreasing order. That invariant is the whole trick.

Scan left to right

Move a pointer i across the array. The current bar is the candidate answer for everything shorter still waiting.

Pop everything shorter

While the stack’s top bar is shorter than arr[i], pop it — its next greater element is arr[i]. Record the answer.

Push the current bar

Now arr[i] joins the stack to wait for its next greater element. The stack stays decreasing.

Whatever’s left has no answer

Bars still on the stack at the end never found a taller neighbor — their next greater element is “none”.

Time

O(n)

Space

O(n)

Each element

pushed 1×, popped ≤1×

Brute force

O(n²)

The code

# next greater element for every index, O(n) def next_greater(arr): n = len(arr) ans = [-1] * n stack = [] # indices, values decreasing for i in range(n): while stack and arr[stack[-1]] < arr[i]: ans[stack.pop()] = arr[i] # resolved! stack.append(i) return ans # leftovers stay -1

Store indices, not values, so you can also compute distances (as in "daily temperatures": how many days until a warmer one). Flip the comparison to > for next-smaller; scan right-to-left for previous greater/smaller. Four problems, one skeleton.

Quick check

1. Why is the stack always in decreasing order?

2. There’s a while-loop inside the for-loop. Why is it still O(n)?

FAQ

What is a monotonic stack?

A stack kept in sorted order — always increasing or always decreasing — by popping elements that would break the order before pushing a new one. It turns "nearest larger/smaller neighbor" questions into a single linear pass.

Why store indices instead of values?

Indices let you recover both the value (arr[idx]) and the distance (i - idx). Problems like "daily temperatures" need the distance, so indices are the more general choice.

What problems use a monotonic stack?

Next/previous greater or smaller element, daily temperatures, largest rectangle in a histogram, trapping rain water, stock span, and remove-K-digits. Any "nearest bigger/smaller" pattern is a candidate.

Increasing or decreasing stack — which do I use?

For next-greater you keep values decreasing (pop when a bigger one arrives). For next-smaller, keep them increasing. Pick the order so the element that "resolves" a waiting item is the one that breaks the invariant.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

The Monotonic Stack.

How it works

Scan left to right

Pop everything shorter

Push the current bar

Whatever’s left has no answer

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Scan left to right

Pop everything shorter

Push the current bar

Whatever’s left has no answer

The code

Quick check

FAQ

Keep going

Stacks & Queues →

Valid Parentheses →

Sliding Window →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.