Monotonic stacks collapsed my O(n²) into one pass

A monotonic stack is a stack whose elements stay in strictly increasing or decreasing order. You pop whatever breaks the order before you push the next element. Interview rounds test whether you recognize the pattern in "scan forward until something bigger happens" problems.

Monotonic stack is the pattern that makes senior engineers say "oh, that's clever" and mid-level engineers say "how was I supposed to see that?" The gap between those two reactions is smaller than it looks, and I want to close it in one post.

Here's the gap in one paragraph. The naive solution to "for each day's temperature, how many days until a warmer one?" is two nested loops: for each day, scan forward until you find a warmer day, then record the distance. That's O(n²). It runs fine on LeetCode's small test cases. It times out on the big ones. Somewhere in the middle of your interview you realize the naive loop is going to TLE, and now you need an O(n) solution in eight minutes without ever having seen the trick.

The trick is one question. I'm going to name it up front so you can carry it with you into every future problem that smells like "scan forward until something happens."

The One Question

When you see a problem that asks "for each element, what's the next (greater / smaller / bigger / closer) one?" or "how long until this thing is resolved?" or "find the boundaries of each peak," ask yourself:

What is each element waiting for, and what happens when it finally arrives?

That's it. If you can name "element at index i is waiting for the first element to the right that's greater than it," then you are already writing a monotonic stack solution, because the stack is literally the queue of elements that haven't gotten what they're waiting for yet. When a new element shows up and is what somebody was waiting for, that somebody pops off the stack and records its answer. The stack stays monotonic because any element whose wait has been satisfied is gone, and everything that's still on the stack is still waiting — which means the new arrivals have to respect the ordering of who's been waiting the longest.

I promise this sounds more mystical than it is. Let me show you what I mean on the classic problem.

Daily Temperatures: Waiting For Warmer

Here's the problem: given an array of daily temperatures temps, for each day return the number of days you have to wait until a warmer temperature. If no warmer day exists, return 0.

Example: temps = [73, 74, 75, 71, 69, 72, 76, 73] Expected output: [1, 1, 4, 2, 1, 1, 0, 0]

The naive O(n²) approach is obvious. The O(n) approach is where the stack comes in. Watch closely — I'm going to narrate the stack's state after each iteration, because the narration is what makes the pattern click:

Final output: [1, 1, 4, 2, 1, 1, 0, 0]. ✓

Now read that table one more time, but this time think about what's on the stack. At every point in the walk, the stack contains exactly the days that are still waiting for a warmer day. The waiters are ordered newest-on-top, because the oldest ones have been waiting the longest and have the strictest bar to clear.

And here's the load-bearing observation: the stack is monotonic decreasing by temperature from bottom to top. It has to be. If any newer element were warmer than an older element, the older one would already have popped. Monotonic decreasing is a consequence of the wait, and is the invariant the entire algorithm maintains — not a separate rule you memorize.

PYTHON

Copy

def daily_temperatures(temps): result = [0] * len(temps) stack = [] # indices of days still waiting for a warmer day for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: waiting_day = stack.pop() result[waiting_day] = i - waiting_day stack.append(i) return result

Seven lines. Every line maps directly to a sentence in the English description. The while loop is "keep popping waiters who just got what they wanted." The append is "this new day is now waiting too." You did not need to know the pattern name to write this if you could name the wait.

The Mental Picture

Here's a state diagram of what happens at each step. Read it as a traffic light for the stack: every new element either gets waved through (pushed) or is the thing some waiters were waiting for (pops some, then pushed).

Diagram

Copy source

Rendering diagram...

That loop — check, maybe pop, maybe push again — is the entire pattern. The while inside the for loop is where the amortized O(n) magic happens, and I want to pause on it for a second because this is the thing most "monotonic stack tutorial" posts fail to explain.

Why It's Actually O(n) (Amortized)

Look at the code again:

PYTHON

Copy

for i, t in enumerate(temps): # O(n) outer loop while stack and temps[stack[-1]] < t: # inner loop — looks like another O(n) ... stack.append(i)

A nested loop looks like O(n²) at first glance. The naive worry is that for some element, the while might pop a lot of stack entries, and if that happens for every element, you're back to quadratic.

Except it can't happen for every element. The entire stack, across the lifetime of the algorithm, has exactly n total pushes (one per element in the input). And since every pop is preceded by a push, there can be at most n total pops across the entire algorithm. The inner while loop might run 0 times on one iteration and 5 times on another, but its total work across all iterations is bounded by n.

Total work = pushes (n) + pops (≤ n) = O(n) in time complexity.

This is textbook amortized analysis. Robert Tarjan formalized it in his 1985 paper Amortized Computational Complexity (SIAM Journal on Algebraic and Discrete Methods), and the stack case is the canonical teaching example in Cormen et al., Introduction to Algorithms chapter 17 under the "accounting method." Each push pays for its own eventual pop up front. When the pop actually happens, it's free because it was already prepaid.

If an interviewer asks you why this is O(n) and not O(n²), give them the amortized-analysis answer: "each element is pushed at most once and popped at most once, so the total work across all iterations of the inner loop is bounded by n." That one sentence distinguishes candidates who've memorized the pattern from candidates who understand it.

Increasing vs Decreasing: The Wait Tells You Which

The other thing every tutorial tries to cram into your head is "monotonic increasing stack" vs "monotonic decreasing stack," as if those were separate patterns you pick between by remembering a table. They're not. The wait tells you which.

The rule is: the stack stays monotonic in the direction opposite to what each element is waiting for. Waiting for greater? The stack top is the smallest waiter, so the stack is decreasing. Waiting for smaller? The stack top is the largest waiter, so the stack is increasing. You can re-derive this in ten seconds during an interview if you can name the wait. You should never memorize it.

Here's the decision path as a diagram — you name the wait, the stack type follows automatically:

Diagram

Copy source

Rendering diagram...

If you can draw this from memory during an interview, you're done. The wait determines the stack. The stack determines the pop condition. The pop condition determines the code.

Next Greater Element: Same Pattern, Different Return Value

PYTHON

Copy

def next_greater_elements(nums): result = [-1] * len(nums) stack = [] # indices still waiting for a greater number for i, n in enumerate(nums): while stack and nums[stack[-1]] < n: result[stack.pop()] = n stack.append(i) return result

This is literally the same code as Daily Temperatures with two tiny changes: result[waiting_day] = i - waiting_day becomes result[stack.pop()] = n (because now we want the value, not the distance), and the default is -1 instead of 0. The wait is the same wait. The monotonic property is the same monotonic property.

If you're in an interview and the problem is "next greater element, but circular, you can wrap around," you don't need a new trick. You just iterate the array twice (conceptually — use i % n) and the same stack picks up everything that was still waiting at the end of the first pass. One-line change: for i in range(2 * len(nums)): with n = nums[i % len(nums)] inside. Same wait, longer circle.

Largest Rectangle in Histogram: The Hard One

Now the hard one. Given an array of bar heights, find the area of the largest rectangle that fits entirely within the histogram.

The naive solution is O(n²): for each bar, expand left and right until you hit a shorter bar, record the width × height, take the max. That times out on big inputs, and the interviewer knows it. You need O(n).

Here's the wait. For each bar, the rectangle it's the shortest member of has two boundaries: the first shorter bar to its left, and the first shorter bar to its right. Everything between those two boundaries is at least as tall as this bar, so you can fit a rectangle of this height all the way across.

So each bar is waiting for the first shorter bar on its right. When that shorter bar arrives, we can compute the rectangle: height = the waiting bar's height, width = (the shorter bar's index) − (the first shorter bar to the left of the waiting bar) − 1. The left boundary is the new stack top after we pop the current element, because the stack is monotonic increasing and everything still on it is shorter than what we're popping.

This is the hard one because you're computing two things with one stack, and the index arithmetic is fiddly. Here's the reference implementation:

PYTHON

Copy

def largest_rectangle_area(heights): stack = [] # indices of bars whose right boundary is still unknown max_area = 0 # Sentinel: append a 0-height bar at the end to force all remaining waits to resolve for i, h in enumerate(heights + [0]): while stack and heights[stack[-1]] > h: top_idx = stack.pop() top_height = heights[top_idx] # Width = right boundary (i) - left boundary (new stack top) - 1 width = i if not stack else i - stack[-1] - 1 max_area = max(max_area, top_height * width) stack.append(i) return max_area

Two things to notice. First, the sentinel trick: appending a 0-height bar at the end guarantees every bar's wait resolves by the end of the loop. Without it, you'd need a second pass to drain the stack, which works but reads worse and is harder to explain under pressure. This is the same trick that shows up in linked-list problems as a sentinel node — a dummy element that exists only to make the loop invariant cleaner. LeetCode's own editorial solution for problem 84 uses the same sentinel pattern and credits it for halving the code.

Second, the width calculation. When you pop a bar at index top_idx, the right boundary of its rectangle is i (the current bar, the one that's shorter). The left boundary is the new stack top (the closest shorter bar to its left), because everything between the left and right boundaries on the stack has already been popped — they were all at least as tall as top_height. So width = i - stack[-1] - 1 (if the stack isn't empty) or width = i (if the popped bar was taller than everything before it, meaning its rectangle goes all the way to the left edge).

This index arithmetic is the part that trips people up in interviews. The fix is not to memorize the formula — it's to draw the picture. Draw a histogram, pick a bar, draw the rectangle, label the left and right boundaries. The formula writes itself. If you can't draw it, you can't code it, and staring at the code won't help.

Common Failure Modes

These are the real bugs I see in coaching sessions, in order of how often they show up.

Failure 1: Storing values on the stack instead of indices

PYTHON

Copy

stack.append(temps[i]) # wrong — now you can't compute i - waiting_day

You almost always want the index on the stack, not the value, because the problem usually asks for a distance (Daily Temperatures) or a range (Histogram). Store the index. If you need the value, look it up: temps[stack[-1]].

Failure 2: Getting the comparison strict/non-strict wrong

PYTHON

Copy

while stack and temps[stack[-1]] <= t: # ← sometimes wrong while stack and temps[stack[-1]] < t: # ← sometimes wrong

Which one is right depends on whether the problem wants "strictly greater" or "greater or equal." Daily Temperatures wants strictly warmer (<). Largest Rectangle wants strictly shorter when popping (>), but if you use >= you can often get away with it because equal-height bars don't change the max area. The failure mode is either being inconsistent between problems or being confidently wrong on one edge case in the interview. The fix: walk a 3-element example by hand before writing code, and check which comparison matches the problem statement.

Failure 3: Forgetting to drain the stack at the end

PYTHON

Copy

for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: ... stack.append(i) return result # ← anyone still on the stack has their default answer

For Daily Temperatures this is fine — the default is 0 and the elements still on the stack never found a warmer day, so 0 is correct. For problems where you need to resolve every wait (Histogram, for example), you either drain the stack after the loop or use the sentinel trick (append a terminating element that guarantees all waits resolve during the loop). The sentinel is cleaner. Use it.

Failure 4: Using a monotonic stack for problems that aren't actually monotonic

Not every "look back until" problem is a monotonic stack problem. If the thing you're looking for has a nonlinear relationship with your current position (e.g., "the closest day whose temperature differs by less than 5"), a monotonic stack does not work and you need a different structure — usually a balanced BST, a segment tree, or a sorted container. The monotonic stack only works when the wait is monotone in one direction. If the wait is "first greater" or "first smaller," you're fine. If it's "first within a range" or "first divisible by k," you're not.

The Interview Talk-Track

Here's how to narrate this pattern out loud so an interviewer can grade you on reasoning, not memorization:

1. Name the wait. "Each element is waiting for the first element to the right that's strictly greater than it. That's a classic monotonic stack setup."
2. Pick index or value. "I'll store indices on the stack because the problem asks for distances, so I need to know where the waiting element came from."
3. Name the pop condition. "I pop when the new element is greater than the stack top — that means the top just got what it was waiting for."
4. State the O(n) argument before they ask. "This is amortized O(n) because each index is pushed once and popped once across the whole algorithm."
5. Walk the small case. Pick [73, 74, 75, 71] and trace the stack out loud. Catches off-by-ones, shows the interviewer you can debug by reading, not by running.

If you do those five steps, the interviewer sees a candidate who understands the why. The candidates who only remember "monotonic stack for next greater element" get stuck the moment the problem is rephrased — circular arrays, 2D histograms, stock spans — and they can't re-derive. The wait framing is the re-derivation engine.

Citations and Further Reading

• Robert Tarjan, "Amortized Computational Complexity" (SIAM 1985). DOI:10.1137/0606031. The foundational paper. If you want to see where the amortized-O(n) argument comes from in its original form, this is the root citation.
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, chapter 17 "Amortized Analysis." MIT Press. The academic standard reference. The stack example with the push/pop accounting method is the teaching case for the whole chapter.
• LeetCode editorial for problem 84 (Largest Rectangle in Histogram). leetcode.com/problems/largest-rectangle-in-histogram/editorial. The sentinel-stack solution and index-arithmetic walk-through. Free to read without a Premium subscription on most editorial pages.
• Steven & Felix Halim, Competitive Programming 4, section on stack-based problems. cpbook.net. The canonical reference for contest-style problems where monotonic stack shows up, including tight-loop optimizations that matter in contest timing but rarely in interviews.

The Takeaway

Monotonic stack is one question: what is each element waiting for? Every piece of the pattern — when to push, when to pop, whether the stack is increasing or decreasing, why it's O(n) — follows from the wait. The stack is the waiting room. The while loop is the bouncer letting people out when their ride shows up. The monotonic property is a consequence, not a rule to memorize.

If you only remember one thing from this post, let it be the habit of asking what's the wait? out loud before you touch the keyboard. Say it to the interviewer, say it to yourself on the whiteboard, say it into the quiet of your kitchen at 11pm when you're grinding LeetCode alone. Once you name the wait, the stack writes itself, and you never have to guess whether it's "increasing" or "decreasing" again.