A monotonic stack is a plain stack with one extra rule: you keep its contents sorted (always increasing, or always decreasing) by popping anything that would break the order. That tiny discipline turns a whole family of "find the next bigger / smaller element" problems from O(n²) into a single O(n) pass.
Core idea. March through the array once, keeping a stack of indices whose values are strictly decreasing. When a new value is bigger than the value at the top of the stack, it is the next greater element for that index — so pop it, record the answer, and repeat.
The classic problem: Next Greater Element. For each item, find the first item to its right that is larger; if there is none, the answer is -1. For nums = [2, 1, 2, 4, 3] the answer is [4, 2, 4, -1, -1].
Intuition
Imagine a line of people of different heights, all facing right, and you want to ask each person: "who is the next taller person ahead of you?" A short person standing behind a tall one is blocked — they can only see someone taller once a taller person appears further down the line.
The stack is exactly that line of "still waiting to be answered" people. Everyone shorter than the newcomer can finally see them, so they get their answer and step out of line. The newcomer then waits behind whoever is left — and because we always pop the shorter ones first, the people still waiting are always in decreasing height order from bottom to top.
Walk through it
Step through the animation on the right. The i pointer scans nums left to right. The vertical stack holds indices that are still waiting for a bigger number; its values always decrease from bottom to top.
Watch index 2 (value 2): when i reaches it, the value 1 on top of the stack is smaller, so 2 pops index 1 and writes res[1] = 2. Then watch index 3 (value 4): it is bigger than everything waiting, so it pops twice in a row — clearing both the 2 at index 2 and the 2 at index 0 — and fills in res[2] = 4 and res[0] = 4. At the end, indices 4 and 3 are still on the stack: nothing bigger ever came, so they keep their -1.
The code, line by line
def next_greater(nums):
n = len(nums)
res = [-1] * n
stack = [] # indices, values decreasing
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
top = stack.pop()
res[top] = nums[i] # nums[i] is its next greater
stack.append(i)
return res # leftovers keep -1resstarts as all-1, so any index that never gets popped already has the correct "no answer" value.- The stack stores indices, not values — we need the index to write into
res, andnums[stack[-1]]gives us the value at the top. - Line 6 is the heart of it: while the top of the stack is smaller than the current value, the current value is its next greater element.
- Lines 7–8 pop that index and record
nums[i]as its answer. Thewhilekeeps popping, so one big value can resolve many waiting indices at once. - Line 9 pushes the current index — it now waits for its own next greater element.
Complexity
| Case | Time | Notes |
|---|---|---|
| Time | O(n) (moderate) | each index is pushed once and popped at most once |
| Space | O(n) (moderate) | the stack can hold every index in the worst case |
O(n) (moderate)The pass looks like it has a nested loop, but the inner while is bounded by the total number of pops — and every index can be popped only once. So the combined work is 2n operations, which is O(n). A reverse-sorted array (e.g. [5, 4, 3, 2, 1]) is the worst case for space: nothing ever pops, so all n indices pile up on the stack.
When to use / pitfalls
Reach for a monotonic stack whenever a problem says "next/previous greater/smaller element," or asks about spans, ranges, or "how far until something bigger." Daily Temperatures, Largest Rectangle in Histogram, Trapping Rain Water, and Stock Span are all the same move. The signal: you want a nearby element related by an inequality, and a brute-force scan would be O(n²).
Two mistakes trip people up. First, store indices, not values — you almost always need the position
to write the answer or compute a distance. Second, mind the comparison: < versus <= decides
whether equal values pop each other. For strictly-greater "next greater element," keep it < so
equal values do not resolve one another.
Practice
For nums = [2, 1, 2, 4, 3], how many indices does the value 4 (at index 3) pop off the stack when i reaches it?
1. Why does the stack store indices instead of values?
2. What invariant does the stack maintain from bottom to top?
3. Why is the algorithm O(n) despite the inner while loop?
4. For nums = [2, 1, 2, 4, 3], what is the final answer array?