You have an array. For each element, find the next element to its right that is bigger than it. The brute-force answer is two nested loops: O(n²). The interview answer is one pass with a stack: O(n). And once you see the pattern, you will recognise it in at least ten classic problems.
The idea in one paragraph
A monotonic stack keeps its elements in sorted order — increasing or decreasing. You walk the array once. Each element is pushed once and popped at most once, which is why the whole thing is O(n). The trick is what a pop means: when a new element breaks the order, it resolves every element waiting on the stack that it beats.
The cleanest first example is LeetCode 739, Daily Temperatures: for each day, how many days until a warmer one?
def dailyTemperatures(temperatures):
answer = [0] * len(temperatures)
stack = [] # indices of days waiting for a warmer day
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
The stack holds indices in decreasing temperature order. A day sits on the stack, unresolved, until a warmer day arrives and pops it. That warmer day is exactly the answer for every day it pops. Nothing is ever revisited.
The four variants
Flip two choices — the comparison, and which direction you scan — and you get four tools:
| Scan | Comparison | Answers |
|---|---|---|
| Left to right | pop while stack top < current
|
Next greater element |
| Left to right | pop while stack top > current
|
Next smaller element |
| Right to left | pop while stack top < current
|
Previous greater element |
| Right to left | pop while stack top > current
|
Previous smaller element |
Most problems are one row of this table plus a small twist. Learn the table and you stop memorising solutions.
The practice ladder
Work these in order. Each one adds exactly one new idea:
- 496. Next Greater Element I (Easy) — the pure form. Build a map from value to next greater, then answer the queries.
- 739. Daily Temperatures (Medium) — same shape, but record the index distance instead of the value.
-
503. Next Greater Element II (Medium) — the array is circular. Run the same loop over
2nindices withi % n. -
901. Online Stock Span (Medium) — collapse consecutive days the current price dominates. Store
(price, span)pairs on the stack and accumulate spans as you pop. - 402. Remove K Digits (Medium) — a greedy deletion: pop while the top is bigger than the current digit and you still have deletions left.
- 456. 132 Pattern (Medium) — scan right to left with a decreasing stack, tracking the largest valid "2" seen so far.
- 84. Largest Rectangle in Histogram (Hard) — the boss fight. For each bar, the stack finds how far left and right it can extend before hitting a shorter bar. Area = height × width. Add a sentinel zero at the end to flush the stack.
- 85. Maximal Rectangle (Hard) — build a histogram row by row from the matrix, then run problem 7 on each row.
- 42. Trapping Rain Water (Hard) — the stack version: when a bar pops, the water above it is bounded by the new stack top on the left and the current bar on the right.
- 1944. Number of Visible People in a Queue (Hard) — each person sees everyone until the first taller person, plus that taller person. A decreasing stack counts exactly that.
How to spot it in an interview
Listen for the shape of the question, not the story: "next greater / smaller", "how many days until", "span", "how far can this extend", "first element that breaks the pattern". If the question is about each element's relationship to its nearest bigger or smaller neighbour, reach for the stack before you reach for the nested loop.
Two practical tips. First, store indices, not values — you almost always need the position for the answer or the width. Second, decide the comparison by asking what a pop should mean: if popping should resolve "I found something bigger", pop while the top is smaller.
The pattern is small enough to learn in an afternoon and shows up often enough to pay for that afternoon many times over. Do the ladder in order, and by problem 7 you will be writing the template from memory.
Top comments (0)