The Monotonic Stack

Linear Data Structures · 30 min

DSA · Stacks · Pattern

The Monotonic Stack

Finding the next greater element looks like it needs a nested loop. Keep the stack ordered while you scan and the whole thing collapses into one pass — every index goes on once and comes off once.

Step through 2 1 5 6 2 3 →
input · 2 1 5 6 2 3
→
next greater · 5 5 6 −1 3 −1

01 The idea

Throw away what can never be the answer

You are given an array. For every position you want the first value to its right that is bigger. The obvious plan is to stand on each position and walk right until you find one. That walk re-reads the same values again and again.

Now scan left to right instead, and keep a pile of positions that are still waiting for an answer. The moment you pick up a value bigger than the top of that pile, that value is the answer for the top — and for everything under it that is also smaller. So you pop, answer, pop, answer. What survives on the pile never increases from bottom to top — strictly decreasing when the values are all different, flat where two of them tie. That ordering is why it is called a monotonic stack.

Scan left to right. While the top of the stack is smaller than the value you are holding, that value is its answer — pop it and write the answer down. Then push where you are standing.
Monotonic stackA stack whose values stay in one direction from bottom to top. Here they never increase as you climb, so the first item that refuses to pop tells you everything deeper refuses too.
Next greater elementFor position i, the first value to the right of i that is strictly larger than a[i]. If no such value exists the answer is −1.
Amortised O(n)One step can pop many items, but across the whole run each index is pushed once and popped at most once. Total work is proportional to n, not n².

02 Hand trace

2 1 5 6 2 3, one index at a time

Six values: 2 1 5 6 2 3. The stack holds indices, written here as the values they point at with the top on the right. Follow index 0 — it is pushed in round 0, sits untouched through round 1, and is finally answered by 5 in round 2. Green notes are steps that settled an answer; red notes are steps that settled nothing.

i = 0, 12156232 then 1 — nothing to pop. stack [2, 1]
i = 2 · v=52156235 pops 1 → ans[1]=5, then pops 2 → ans[0]=5. stack [5]
i = 3 · v=62156236 pops 5 → ans[2]=6. stack [6]
i = 4 · v=22156236 is not smaller than 2 — nothing pops. stack [6, 2]
i = 5 · v=32156233 pops 2 → ans[4]=3, then 6 blocks. stack [6, 3]
result556−13−16 and 3 were never beaten → −1 each

Index 1 landed on top of index 0 at the end of round 1, and neither of them was touched again until round 2, when 5 cleared both in one move. Nobody re-read anything: seven value comparisons settled all six answers. The code in section 03 is this trace written down.

03 Naive vs improved

Two loops, or one loop and a stack

Both return the same array. The left one re-reads the tail for every position. The right one reads each position twice — once on the way onto the stack, once on the way off.

Brute force · O(n²)

for i = 0 to n-1:    ans[i] = -1    for j = i+1 to n-1:        if a[j] > a[i]:            ans[i] = a[j]; breakreturn ans

Monotonic stack · O(n)

stack = empty   # indices; top = last pushedfor i = 0 to n-1:    while stack not empty and a[top] < a[i]:        ans[pop()] = a[i]    push ifor each i left on stack: ans[i] = -1return ans

The inner loop is gone. Line 3 on the left restarts at i+1 every time, so the same tail is read over and over. The stack already holds every position still waiting for an answer, in the exact order they will be answered, so there is nothing left to re-scan.

Why the stack stays ordered. Line 3 on the right removes everything smaller than a[i] before line 5 pushes i, so a[i] is never bigger than the value below it. That invariant is what lets you stop at the first value that does not pop — everything deeper is at least as big.

Strictly smaller, not smaller-or-equal. Using < on line 3 leaves equal values sitting on the stack, so an equal value is never reported as "greater". Loosen it to <= and you get the next greater-or-equal element instead. Interviewers toggle this one operator on purpose.

Line 6 is the −1 case. Anything still on the stack when the scan ends was never beaten by anything to its right. In the trace that was index 3 (value 6) and index 5 (value 3).

05 Cheat sheet

The numbers you will be asked for

CaseCostWhy
Time · any inputO(n)Each index is pushed once and popped at most once — at most 2n stack operations in the whole run.
Comparisons · worst≤ 2n − 1Every value comparison either pops something (at most n) or ends one while-loop (at most n − 1).
Extra space · bestO(1)A strictly increasing array pops the single waiting index before every push, so the stack never holds more than one.
Extra space · worstO(n)A strictly decreasing array never pops, so all n indices sit on the stack until the scan ends.
Brute force · worstO(n²)On 6 5 4 3 2 1 position i scans all n − 1 − i cells and still finds nothing: 15 comparisons for n = 6.
One passLeft to right, index by index, no backtracking and no second scan over the data.
Indices, not valuesThe answer has to be written back to the right slot, and distance problems need the index anyway.
Flip the comparison< gives next greater. Flip to > and the stack stays increasing, giving next smaller. Same seven lines.

06 Where & why

When the stack is the right tool

A monotonic stack is not a general speed-up. It pays off for exactly one shape of question: for every element, find the nearest element on one side that beats it under some comparison. Outside that shape it buys you nothing.

Reach for it when…

The question says "next" or "nearest"Next greater temperature, previous smaller price, nearest taller building. That word is the signal.
Old items are answered by new onesThe answer for a position is discovered while you stand on a later position, so you never walk backwards.
You need spans or widthsLargest rectangle in a histogram and stock span are both "how far can I stretch before someone blocks me".
n is large and the scan is quadraticThe brute force costs about n²/2 comparisons at worst. At n = 10⁵ that is 5 × 10⁹; the stack does under 2 × 10⁵.

Use something else when…

SituationBetter choiceWhy
You want the largest value to the right, not the next oneSuffix maximumOne backward pass with a running maximum answers it. No stack, no popping rule, no invariant to defend.
You need the maximum over arbitrary query rangesSparse table or segment treeA stack answers one fixed question per index. Arbitrary ranges need a structure built for queries.
You need how many elements to the right are greaterFenwick tree over sorted valuesThe stack throws away everything it pops, so it can report the nearest but never a count.
The values arrive one at a time and you need answers immediatelyPrevious-side variantNext greater needs the future. Rewrite the question as a previous-greater query, which a stack can answer online.
In an interview the monotonic stack is a pattern, not a data structure. Nobody asks you to implement a stack. They ask a question shaped like "the nearest bigger thing" and watch whether you reach for the nested loop or for the pop.

07 Interview questions

Answer these out loud

Each answer is about twenty seconds spoken. Say the direct answer first, then the reason.

What is a monotonic stack?
A stack you maintain so its contents stay ordered in one direction from bottom to top. You enforce it by popping everything that would break the order before you push. For next greater element the stack stays decreasing, so the first item that refuses to pop marks the boundary and you can stop.
Walk me through next greater element using one.
Scan left to right holding indices on the stack. While the value at the top is smaller than the current value, pop it and record the current value as its answer. Then push the current index. Anything still on the stack when the scan ends gets -1.
That is a while loop inside a for loop. Why is it not O(n²)?
Because the inner loop is bounded across the whole run, not per iteration. Each index is pushed exactly once and popped at most once, so the while body runs at most n times in total. Add the n pushes and you get O(n). That is amortised analysis: one iteration can be expensive, but the total across all of them is linear.
What invariant does the stack keep, and why is the answer correct?
From bottom to top the values never increase, because you pop everything smaller than a[i] before pushing i. With distinct values that is strictly decreasing; the strict < test leaves equal values sitting side by side. That gives the stopping rule: the first value that refuses to pop means everything under it also refuses. It also gives correctness — if index t is still on the stack when you reach i, no index between them was bigger than a[t], because such an index would already have popped t.
What is the worst case for space?
O(n), on a strictly decreasing array like 6 5 4 3 2 1. Nothing ever pops during the scan, so all n indices sit on the stack and every answer ends up -1. The best case is a strictly increasing array, where each new value pops the single index waiting before pushing itself, so the stack never holds more than one.
Why push indices instead of values?
Because the answer has to be written back to the right slot. If the stack held values you would know 5 answers some earlier 2, but not which 2. Indices also let you compute distances, which is what problems like Daily Temperatures actually ask for.
Make it return the next greater-or-equal element instead.
Loosen the pop condition to a[top] <= a[i] — one extra character. Equal values now get popped and answered. With strict < an equal value stays on the stack and waits for something genuinely larger.
How would you get the previous smaller element?
Flip the comparison so the stack stays increasing — pop while the top is greater than or equal to a[i] — and read the answer from whatever survives on top before you push i. Comparison direction picks greater versus smaller; where you read the answer picks next versus previous. Those two switches give all four variants.
What if the array is circular?
Run the loop over 2n indices and use a[i mod n] for every array access, but only push when i < n. The second lap lets early indices be answered by values that wrap around. Complexity stays O(n) because there are still at most n pushes and n pops.
When is the brute force actually fine?
When n is small or the array is close to increasing, since the inner walk then stops on its first step. On 2 1 5 6 2 3 both versions do exactly 7 comparisons, so the stack wins nothing. The gap only opens on long decreasing runs — at n = 10⁵ a decreasing array costs the brute force around 5 × 10⁹ comparisons and the stack under 2 × 10⁵.
Where would you use this outside a puzzle?
Anywhere the question is "the nearest thing that beats me". Daily Temperatures, Stock Span, Largest Rectangle in a Histogram and Trapping Rain Water are all this loop with a different value recorded on the pop. In production the same shape turns up in expression parsing and in time-series analytics, where "the next day the price exceeds today" is a next greater element query.

08 Practice problems

Six problems, one pattern

Every one of these is the same loop with a different thing recorded on the pop. Solve them in order; the twist is the part worth thinking about.

Next Greater to the Right

Easy
Given an array, return an array where position i holds the first value to the right of i that is strictly larger than a[i], or -1 when there is none.
Follow-up
Handle the leftover stack without a second loop — fill the answer array with -1 before the scan starts and check that nothing else has to change.
Show the hint
The only line that ever writes a real answer is the pop line; every untouched slot keeps whatever you initialised it to.

Previous Smaller Element

Easy
For each position return the nearest value to its LEFT that is strictly smaller than a[i], or -1 if no such value exists.
Follow-up
The answer is read off the top of the stack before you push, not written on a pop. Same stack, opposite end of the operation.
Show the hint
Decide what happens to a value equal to a[i]. If it is allowed to survive on top you will report something that is not strictly smaller, so the pop test has to cover equality too.

Daily Temperatures

Medium
Given a list of daily temperatures, return an array where position i holds how many days you wait for a warmer day, or 0 if it never gets warmer.
Follow-up
The answer is a distance, not a value — which is exactly why the stack has to hold indices and not temperatures.
Show the hint
On the pop, the answer for the popped index t is i minus t.

Stock Span

Medium
For each day return how many consecutive days ending today, today included, had a price less than or equal to today’s price.
Follow-up
This is a previous-greater query dressed up as a count, and it has to work online — you are not allowed to look at future prices.
Show the hint
Pop while the top price is less than or equal to today’s; the span is i minus the surviving top index, or i + 1 if the stack empties.

Circular Next Greater

Medium
The array wraps around, so after the last element comes the first. Return the next greater element for every position, or -1 if the whole circle has nothing bigger.
Follow-up
Some positions can only be answered by a value that sits before them in the original order, so a single left-to-right pass cannot finish the job.
Show the hint
Loop i from 0 to 2n-1, use a[i mod n] for every read, and only push when i is below n.

Largest Rectangle in a Histogram

Hard
Given bar heights, return the area of the largest rectangle that fits entirely inside the histogram.
Follow-up
Each bar’s rectangle is bounded by the previous smaller bar on the left and the next smaller bar on the right, so one stack has to produce both boundaries in a single pass — and the width is only known at pop time.
Show the hint
When bar t is popped by index i, its right boundary is i and its left boundary is whatever is now on top of the stack, so the width is i minus newTop minus 1.