Stacks and the Monotonic Stack: A Practical Interview Guide

Who asks this, and how oftenInterview frequency: Common

Most asked at Amazon. Here is how often this pattern shows up in each company's coding rounds.

Amazon

Google

If you remember five things

Recognition, the template, and the one-line complexity defense. Everything below is the proof.

The cue. "Next/previous greater/smaller," a distance or span until something beats you, or a histogram area. Those phrases mean reach for the stack before you write a line.
The reframe. A monotonic stack holds candidates still waiting for an answer, and resolves each one the instant its answer walks in. Not "sorted stack," a waiting line.
Store indices. Indices give you the value for free (arr[top]) and distances for free (i - popped). You rarely regret indices, you frequently regret values.
Two knobs. The while comparison picks increasing vs decreasing (and tie handling), and what you write on the pop picks the problem. The real work lives inside the while body.
O(n), and defend it. Each index is pushed once and popped at most once, so the inner while runs at most n times total. That amortized sentence is what separates understanding from memorizing.

1The mental model (what this really is)#

A plain stack is just last in, first out: push, pop, peek the top. Nothing clever.

You use it for matching brackets, undo history, evaluating reverse Polish notation, and simulating recursion when you want to avoid blowing the call stack.
Know those cold. They are the easy warm-ups and they take about five lines each.

The monotonic stack is the interesting one.

It keeps its elements in sorted order, either always increasing or always decreasing from bottom to top.
You enforce that order by popping anything that would break it before you push the new element.
It is never longer than it needs to be, because the instant an element becomes useless you evict it.

Here is the insight that makes it click: the thing you pop is not garbage.

The moment you pop an element, you have learned something exact about it.
For a decreasing stack, when a new bigger value forces a pop, that new value is the first element to the right that is larger than the one you popped.
Not "a" larger element, the very first one, because everything between them was smaller and already got evicted earlier.
You waited, the stack held onto it, and the answer arrived.

The one reframe that unlocks everything

A monotonic stack is a way of holding candidates that are still waiting for an answer, and resolving each one the instant its answer walks in. Stop thinking "sorted stack." Think "a line of people at a counter: I serve each one the moment their match shows up, then they leave and never come back." The people still in line at closing time never got served, and that is a feature. It is how you know they had no answer.

2How to recognize it (the cues in a problem)#

You will not be told to use a stack. You have to smell it. Here are the tells I look for:

Next greater / next smaller, or previous greater / previous smaller. The canonical signal. See those four words together and reach for the stack before you write a line.
Distance or span until a condition is met. "How many days until a warmer temperature." "How far until a taller building." "How many consecutive days the price was at most today." Distance to the next thing that beats you.
Bars, heights, or histograms with an area or rectangle. When the input is a row of heights and the output is an area, the histogram stack is almost certainly the intended O(n) solution.
An obvious nested loop that is O(n^2), with n up to 10^5 or more. That constraint is the interviewer quietly telling you the quadratic scan will time out and they want linear.
Ranges where the current element is the max or the min. Subarray problems where each element "rules" a window, like summing the minimum over every subarray.

One subtler tell: permanent irrelevance.

The answer for an element depends only on elements near it in value and position, and once a better candidate appears, the old one is gone for good.
That "permanently irrelevant once beaten" property is exactly what lets you pop and never look back.
If you can argue "after X shows up, I will never again need Y," you are looking at a monotonic stack.

Pause: a problem asks for "how many days until the price drops below today's," with n up to 100,000. Stack or not, and increasing or decreasing?

Reveal the answer

Stack. "Distance until a condition beats you" plus a quadratic brute force at 100,000 is the cue. You want next smaller, so keep the stack increasing and pop while arr[top] >= arr[i] (the tie choice depends on whether equal counts as "below," which you clarify first). The distance is i - popped.

3The template (how it works, with pseudocode)#

Almost every monotonic stack problem fits this skeleton. Learn the skeleton, then the per-problem work is tiny. I write this exact shape from memory in every round and only change two lines.

stack = []              # usually store INDICES, not values
answer = array of default values, length n

for i in range(n):
    # while the top violates our order given the new element arr[i]
    while stack is not empty and arr[stack.top] < arr[i]:
        popped = stack.pop()
        answer[popped] = i        # or arr[i], or i - popped, etc.
    stack.push(i)

# anything left on the stack never found its answer -> keep default

Two decisions turn this template into a specific solution.

The direction of the comparison (< vs <= vs > vs >= in the while). This decides increasing vs decreasing, and how you handle ties. Get it wrong and you are off by a whole category: you built next-smaller when you wanted next-greater, and the sample case is the one that tells you, if you are lucky.
What you write when you pop. The index of the resolver (i), the distance (i - popped), the value arr[i], or a computed area like height * width. The pop is the moment of truth, so the real work lives inside the while loop. If your while body is empty, you are not using the pattern, you are just iterating.

Store indices, not raw values.

Indices give you the value for free (arr[stack.top]) and distances for free (i - popped).
You rarely regret storing indices. You frequently regret storing values.
The first follow-up is almost always "now return the distance," and if you stored values you have thrown that away.

From the interviewer's chair

When I hand you a next-greater problem, the fastest tell that you actually know this pattern (not just the code) is whether you reach for indices without being prompted. Candidates who store values sail through the happy path, then stall the second I ask for a distance. Narrate the two knobs out loud as you pick them. It reads as command of the pattern, not a lucky recall.

Direction cheat sheet, memorize this:

Next greater element: keep the stack decreasing from bottom to top. Pop while arr[top] < arr[i]. The resolver i is the next greater for everything popped.
Next smaller element: keep it increasing. Pop while arr[top] > arr[i].
Previous greater / smaller: same idea, but the answer for i is whatever is left on the stack top right before you push i. No second pass, no reversed loop, you read the answer off the top as you go.

4A worked example (walk through one problem step by step)#

Take the classic: Daily Temperatures (LeetCode 739). Given temps, for each day return how many days you wait until a warmer day. If none, 0.

Input: [73, 74, 75, 71, 69, 72, 76, 73]

Why not brute force:

For each day, scan forward until warmer. That is O(n^2).
At the real constraint of up to 10^5 days, that is 10^10 operations, dead on arrival.
We want O(n). "Days until warmer" is "distance to next greater element." That is our cue, and it is the whole game.

We keep a decreasing stack of indices. When today's temp beats the day on top, that popped day just found its warmer day: today. The distance is i - popped.

Let me walk it. Stack holds indices, I will show the temps next to them for clarity.

i=0, temp 73. Stack empty. Push 0. Stack: [0(73)].
i=1, temp 74. Top is 73, and 74 > 73, so day 0 found its warmer day. Pop 0, answer[0] = 1 - 0 = 1. Stack empty now. Push 1. Stack: [1(74)].
i=2, temp 75. 75 > 74, pop 1, answer[1] = 2 - 1 = 1. Push 2. Stack: [2(75)].
i=3, temp 71. 71 < 75, order holds, nobody gets resolved. Push 3. Stack: [2(75), 3(71)].
i=4, temp 69. 69 < 71, holds. Push 4. Stack: [2(75), 3(71), 4(69)].
i=5, temp 72. Now 72 > 69, pop 4, answer[4] = 5 - 4 = 1. Next top is 71, and 72 > 71, pop 3, answer[3] = 5 - 3 = 2. Next top is 75, 72 < 75, stop. Push 5. Stack: [2(75), 5(72)].
i=6, temp 76. 76 > 72, pop 5, answer[5] = 6 - 5 = 1. 76 > 75, pop 2, answer[2] = 6 - 2 = 4. Stack empty. Push 6. Stack: [6(76)].
i=7, temp 73. 73 < 76, holds. Push 7. Stack: [6(76), 7(73)].

End of array. Indices 6 and 7 are still on the stack. They never found a warmer day, so they keep the default 0.

Final answer: [1, 1, 4, 2, 1, 1, 0, 0].

Notice the burst at i=5 and i=6.

A single new element resolved several waiting days at once: i=5 cleared two days, i=6 cleared two more.
That is the magic, and it is also where people panic and think "nested loop, this must be O(n^2)." It is not.
Each index is pushed exactly once and popped at most once, so across the whole run there are at most 8 pushes and 8 pops for this 8-element input.
Some steps do several pops, some do zero, but the total work is linear. Say that out loud when you code it. The interviewer is watching for exactly that understanding.

5Variations and gotchas#

Increasing vs decreasing.

Decreasing stack finds next greater. Increasing stack finds next smaller.
Flip the while comparison, flip the meaning.
Write it on your scratch paper before coding so you do not flip it in your head mid-loop. I have watched strong candidates lose ten minutes because they mentally swapped the two under pressure and could not see why the output was reversed.

Previous vs next.

Everything above resolves elements as you move right, so you naturally get "next" answers.
For "previous greater/smaller," do not reverse anything fancy. The answer for the current index is simply what sits on the stack top the moment just before you push it.
Peek, record, then push. One extra line, that is the whole trick.

Strict vs non-strict (ties).

< vs <= is where off-by-one bugs hide.
If duplicates should resolve each other, use the comparison that pops on equality. If equal elements should not count as "greater," do not pop on equal.
In histogram area problems this choice decides whether you double count or undercount widths, and the area can land off by a full bar.
Trace one concrete tie case by hand, for example two bars of height 2 side by side, and see what each comparison does.

Circular arrays.

"Next greater element in a circular array" (LeetCode 503) is a favorite twist.
Loop 2n times and index with i % n, but only push during the first pass (or guard) so each real index is pushed once.
The second pass just resolves leftovers that wrap around, and because each real index is pushed only once, it stays O(n).

Sentinels.

For histogram-style problems, appending a 0 height (or a -infinity / +infinity guard) at the end forces the stack to flush everything, so you skip separate cleanup after the loop.
One extra element, and your post-loop drain logic disappears.
A clean trick once you see it, and it kills a whole class of "forgot the leftovers" bugs.

Monotonic deque, not stack.

Sliding window maximum (LeetCode 239) needs a monotonic deque because you pop from both ends: front to drop elements that left the window, back to maintain order.
Same family, one more degree of freedom.
Moving window plus "max/min in window" means deque, not stack.

6Complexity#

Time is O(n). This surprises people, because there is a loop inside a loop.

Each element is pushed exactly once and popped at most once across the entire run.
Total pushes plus pops is bounded by 2n.
The inner while does not reset the work, it drains a budget that earlier pushes already funded.
That is an amortized argument, and saying it out loud signals you understand the pattern rather than pattern matching.
The sentence I keep loaded: "every index enters and leaves the stack at most once, so the inner while across all iterations runs at most n times total, which makes the whole thing O(n)."

Space is O(n) worst case for the stack.

Worst case is input already sorted in the direction that never triggers a pop (think strictly decreasing [5,4,3,2,1] for a next-greater problem, where nothing pops until the end).
The answer array is also O(n).
For the circular variant, still O(n). The 2n loop doubles the constant factor but does not change the order.

7Mistakes that cost people the round#

Storing values instead of indices. Then you need distances and cannot get them. Store indices, derive values. The single most common self-inflicted wound, and it surfaces at the worst moment, when the follow-up asks for a distance you no longer have.
Getting the while comparison backwards. You wanted next greater and built an increasing stack. The output is next smaller and you do not notice until the sample fails. Write the direction down first, before the loop.
The tie bug (< vs <=). Silent, passes the happy path, dies on duplicates. Always test an input with equal neighbors by hand, like [2, 2] or [3, 1, 1, 3].
Forgetting the leftovers. Elements still on the stack at the end never got resolved and must keep their default value. People initialize the answer to garbage or to None and forget this, then return mystery values for the unresolved indices.
Claiming O(n) without being able to defend it. If the interviewer asks "why is this linear, there is a nested loop," and you freeze, it reads as memorization. Have the each-element-pushed-and-popped-once sentence ready and deliver it without hesitating.
Reaching for a stack when a hash map or two pointers is the real answer. Not every "next element" problem is a stack problem. Trapping Rain Water has a clean two-pointer O(1)-space solution that beats the stack. If values are small and bounded, sometimes a counting array wins. Match the tool to the cue.
Over-engineering the easy stack problems. Bracket matching does not need monotonic anything. Do not show off, just push open brackets and pop on close.

Red flag that fails you here

Writing the loop, getting the right answer on the sample, and then going quiet when I ask "why is this O(n) with a nested while?" If you cannot say "each index is pushed once and popped at most once, so total pops are bounded by n," I read the whole solution as recalled, not understood. The amortized sentence is not optional polish, it is the proof that you own the pattern.

8Your practice path#

Do them in this order. Earlier ones build the muscle for later ones. Go implement them yourself without peeking at solutions.

Warm up (plain stacks, Easy):

Valid Parentheses (LeetCode 20)
Min Stack (LeetCode 155)
Baseball Game (LeetCode 682)
Backspace String Compare (LeetCode 844)

Core monotonic stack (Medium, do every one of these):

Next Greater Element I (LeetCode 496)
Next Greater Element II (LeetCode 503, the circular twist)
Daily Temperatures (LeetCode 739)
Online Stock Span (LeetCode 901)
Remove Duplicate Letters / Smallest Subsequence of Distinct Characters (LeetCode 316)
Remove K Digits (LeetCode 402)
132 Pattern (LeetCode 456)
Sum of Subarray Minimums (LeetCode 907)

Boss level (Hard, this is where the pattern pays off):

Largest Rectangle in Histogram (LeetCode 84)
Maximal Rectangle (LeetCode 85)
Trapping Rain Water (LeetCode 42, also solvable two pointer, learn both)
Sliding Window Maximum (LeetCode 239, monotonic deque)

Short on time? Do these four: Daily Temperatures, Next Greater Element II, Largest Rectangle in Histogram, and Sliding Window Maximum. They cover the whole shape of the pattern: distance, circular, area, and the deque variant. Get them to where you can write each cold in under ten minutes and you have covered roughly 90 percent of what these loops actually ask.

9Where this shows up#

This pattern is a staple at the big product companies and in the on-site coding rounds at well-funded startups.

Amazon and Microsoft love the histogram and temperature style questions. Largest Rectangle in Histogram in particular is a recurring Amazon on-site.
Google tends to wrap it inside a larger problem so you have to spot it yourself rather than being handed "find the next greater element." That is exactly why the recognition cues in section 2 matter more than the code.
Trading and quant firms like the span and rolling window flavors because they map onto real time-series work, think rolling maxima on a price feed.
It lands almost entirely in the standard algorithms interview, sometimes as a follow-up to a simpler array question to see if you can push a brute force down to linear when the interviewer says "now make it faster."

The real test is rarely writing the code. It is recognizing, in a problem that mentions none of these words, that you are looking at "resolve each element the moment its answer arrives." Once you see that, the stack writes itself and the rest is just picking the comparison direction and what to record on the pop.

The code is the easy part. The round is won in the five seconds where you name the pattern nobody labeled for you.

Follow-ups the interviewer will ask (and your answers)

"Why is this O(n) when there is a while loop inside the for loop?"

Amortized. Every index is pushed exactly once and popped at most once across the entire run, so total pushes plus pops are bounded by 2n. The inner while does not restart the work, it drains a budget earlier pushes funded. Summed over all iterations, the while body runs at most n times total, so the whole thing is O(n).

"Now return the distance to the next warmer day, not the index."

Already free, because I stored indices. When I pop index popped at position i, the distance is i - popped. If I had stored temperatures I would be stuck and would have to re-walk the array. This is exactly why I store indices by default.

"What changes for a circular array, like next greater element II?"

Loop 2n times and index with i % n so the tail can see the head. I only push real indices once (guard on the first pass), so the second pass only resolves leftovers that wrap around. Each real index still enters the stack once, so it stays O(n) with a doubled constant factor.

"Your histogram area is off by one bar. What is wrong?"

The tie comparison. Equal heights with < versus <= decide whether a bar extends its own rectangle or gets cut at the neighbor, which double counts or undercounts the width by one bar. I trace two equal-height bars by hand, pick the comparison that gives the right width, and add a 0 sentinel at the end so the final flush is handled without separate cleanup.

"Is a stack always the right tool for next-element problems?"

No. Trapping Rain Water has a two-pointer O(1)-space solution that beats the stack, and if values are small and bounded a counting array can win. The cue is "resolve an element once a better candidate appears." If the problem is really two converging pointers or a frequency count, I match the tool to that instead.

What you can now explain in the room

The cues that mean "monotonic stack" even when the problem never says stack: next/previous greater/smaller, span until beaten, histogram area.
Why the stack is a waiting line of unresolved candidates, each served the instant its answer arrives.
The template, and the two knobs (while comparison and what you write on the pop) that specialize it.
Why you store indices, so values and distances both come for free.
The amortized O(n) argument, delivered as one clean sentence under pressure.
The variations interviewers throw: increasing vs decreasing, previous vs next, ties, circular arrays, sentinels, and the deque cousin.

Want to know which companies lean on this in their loops? Check the company guides to see exactly where the monotonic stack tends to show up.

← Previous

Sliding Window

Topological Sort

Get a prep plan built around your Stacks and the Monotonic Stack interview

Tell us the role and your interview date. We will send back a dated, day by day plan. Free.

Thanks. Check your inbox, your Stacks and the Monotonic Stack prep plan is on the way.