Monotonic Stack

Unanswered items wait on a stack until someone bigger arrives.

Brute force: O(n²) — scan ahead from every element
With the pattern: O(n) — each index pushed and popped at most once
Extra space: O(n) — the stack

In plain English

“People line up for a view, shortest at the back. Each newcomer taller than the person in front lets that shorter person finally see their answer — "the first taller person behind me" — and that person leaves the line. Anyone still waiting is shorter than everyone ahead of them, so the line is always neatly ordered.”

Why it's fast

Brute force scans right from every element looking for the next warmer day: O(n²). The stack holds only the days still waiting for an answer, kept in decreasing order. A new day pops every colder day it answers; each index is pushed once and popped once, so the whole thing is O(n).

Spot it when the problem says…

next greater / next smaller element
how many days until a warmer temperature
previous less element
span (consecutive days ≤ today)
largest rectangle in histogram
remove digits to make the smallest number

Visualize

Daily temperatures

For each day, how many days until a warmer temperature? 0 if never.

small numbers under the cells = answer

stack (waiting for a warmer day)

empty

01/30

The stack holds days still waiting for a warmer day. Their temps are always decreasing bottom → top.

Keys: ← → step · space play/pause

pythonline 3

1def daily_temperatures(temps):2    answer = [0] * len(temps)3    stack = []               # indices; temps decreasing4    for i, t in enumerate(temps):5        while stack and temps[stack[-1]] < t:6            j = stack.pop()7            answer[j] = i - j    # i is j's next warmer day8        stack.append(i)9    return answer

How to apply it

01Decide what you need: next greater → keep a decreasing stack; next smaller → increasing stack.
02Push indices, not values, so you can compute distances.
03For each i, while the stack top is beaten by nums[i], pop it and record i as its answer.
04Push i. Anything left on the stack at the end has no answer (default 0 / -1).

Variations you'll meet

Next greater (Daily Temperatures)

The visualizer's example: a decreasing stack of indices still waiting for a warmer day.

python

def daily_temperatures(temps: list[int]) -> list[int]:    ans = [0] * len(temps)    stack = []                      # indices, temps decreasing    for i, t in enumerate(temps):        while stack and temps[stack[-1]] < t:            j = stack.pop()            ans[j] = i - j          # i is j's warmer day        stack.append(i)    return ans

Circular array

Loop i over range(2 * n) and use i % n — the second lap answers elements that wrap around.

Previous + next smaller (histogram)

When a bar is popped, the new top is its left boundary and the current index its right boundary — compute area right then.

python

def largest_rectangle_area(heights: list[int]) -> int:    stack, best = [], 0             # increasing heights    for i, h in enumerate(heights + [0]):        while stack and heights[stack[-1]] >= h:            top = heights[stack.pop()]            left = stack[-1] if stack else -1            best = max(best, top * (i - left - 1))        stack.append(i)    return best

Greedy digit removal

Remove K Digits: pop larger digits from an increasing stack while you still have removals left.

Common mistakes

Pushing values instead of indices, then being unable to compute distances.
Using <= vs < wrongly — matters for duplicates (strictly greater vs greater-or-equal).
Forgetting the sentinel / final flush, so elements left on the stack are never processed (histogram).
Choosing the wrong monotonic direction (increasing vs decreasing) for the question.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved

Think you've got it?

Let the AI interviewer throw a Monotonic Stack problem at you and grade how you explain it.

Mock interview