A stack that stays sorted answers 'next greater element' questions in one pass.
What a monotonic stack is
A stack maintained so its values stay sorted from bottom to top - decreasing for next-greater problems, increasing for next-smaller. The maintenance rule: before pushing a new element, pop everything that violates the order. The magic is in the pops: the arriving element is exactly the answer for every element it pops, because it is the first thing to break their run.
That converts 'for each element, scan right for the next bigger one' - O(n^2) - into one pass where each element is pushed once and popped at most once: O(n) amortized. Same accounting argument as the sliding window's two pointers.
How to recognize it
Signals: 'next greater/smaller element', 'how long until a warmer day', 'span of days since a higher price', 'largest rectangle', 'remove digits to make the smallest number'. The common shape: every element is waiting for the first later (or earlier) element that dominates it.
Also the plain-stack family lives here: matched-pair validation (parentheses) and design questions like min-stack, where an auxiliary stack tracks the running minimum. They share the LIFO discipline even when monotonicity isn't the point.
The pop-and-resolve template
Push indices, not values - the answer is usually a distance or a position, and the value is recoverable from the index. When a new element arrives, every stacked index with a smaller value just met its 'next greater': resolve it during the pop.
pseudocode
# next greater element to the right; -1 if none
answer = [-1] * n
stack = [] # indices; values decreasing
for i in 0 .. n-1:
while stack and a[stack.top] < a[i]:
j = stack.pop()
answer[j] = a[i] # a[i] is j's next greater
stack.push(i)
# indices left on the stack have no next greater
Direction and orientation choices
Four variants come from two switches: greater vs. smaller (decreasing vs. increasing stack) and to-the-right vs. to-the-left (resolve on pop vs. read the stack top at push time). For next-greater-to-the-left, don't scan backwards - at each element, after popping smaller values, whatever remains on top IS the previous greater. Practicing all four orientations once is what makes the pattern automatic.
Common pitfalls
Storing values when the question asks for distance or index - push indices.
Strict vs. non-strict comparison: 'next strictly greater' pops on <, 'next greater or equal' pops on <=. Duplicates make the difference visible; pick deliberately.
Forgetting leftovers: elements still stacked at the end have no answer - initialize the answer array with the sentinel rather than patching afterwards.
Circular arrays (next greater II): iterate indices 0 to 2n-1 with i mod n, pushing only in the first lap - not by concatenating the array.
In histogram problems, missing the sentinel bar of height 0 appended at the end to flush the stack - without it, ascending histograms return 0.
Worked examples
1. Daily temperaturesmedium
For each day, how many days until a warmer temperature? 0 if none ever comes.
Each day waits for the first later warmer day - textbook next-greater, with the answer expressed as a distance, so the stack holds indices.
Keep the stack's temperatures decreasing. When today is warmer than the stack top, today resolves that day: answer[j] = i - j; keep popping.
Push today. Days never popped keep answer 0.
Every index is pushed once, popped at most once: O(n) time despite the nested-looking while, O(n) stack worst case (strictly falling temperatures).
pseudocode
answer = [0] * n
stack = [] # indices, temps decreasing
for i in 0 .. n-1:
while stack and temp[stack.top] < temp[i]:
j = stack.pop()
answer[j] = i - j
stack.push(i)
return answer
Remember: The warm day that pops you is your answer - resolution happens at pop time, and indices on the stack are just days still waiting.
2. Largest rectangle in histogramhard
Given bar heights, find the largest rectangle that fits entirely within the histogram.
The best rectangle using bar j at full height extends left and right until a shorter bar blocks it - so each bar needs its nearest shorter bar on both sides. Nearest-smaller is monotonic stack territory.
One increasing stack finds both sides at once: when bar i is shorter than the stack top, the popped bar's right boundary is i, and its left boundary is the new stack top after the pop.
Width = i - stack.top - 1 (or i when the stack empties - the popped bar was the shortest so far). Area = height x width; track the max.
Append a sentinel height 0 to flush every bar at the end. Each bar pushes and pops once: O(n).
pseudocode
stack = []; best = 0
for i in 0 .. n: # heights + sentinel 0 at i == n
h = (i < n) ? heights[i] : 0
while stack and heights[stack.top] > h:
height = heights[stack.pop()]
width = stack.empty ? i : i - stack.top - 1
best = max(best, height * width)
stack.push(i)
return best
Remember: A bar's rectangle is bounded by its nearest shorter neighbors - and one increasing stack reveals both boundaries at the moment the bar is popped.
3. Valid parentheseseasy
Given a string of (){}[], determine whether every bracket is closed in the correct order.
Correct nesting is last-opened, first-closed - the definition of LIFO, so a stack is the structure, not merely a convenient one.
Push every opener. For a closer, the stack top must be its matching opener: pop on match, fail on mismatch or empty stack (closer with nothing open).
At the end the stack must be empty - leftovers are unclosed openers. Both failure modes matter; candidates routinely check only one.
O(n) time, O(n) worst-case stack. A map from closer to opener keeps the code branch-free.
pseudocode
pairs = { ')':'(', ']':'[', '}':'{' }
stack = []
for ch in s:
if ch is an opener: stack.push(ch)
else:
if stack.empty or stack.pop() != pairs[ch]: return false
return stack.empty
Remember: Nesting is LIFO by definition - and validity has two failure modes: a closer with no match, and openers left unclosed at the end.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Why is the monotonic stack pass O(n) despite a while-loop inside the for-loop?
The while-loop rarely executes
✓ Each element is pushed exactly once and popped at most once, so total stack operations are bounded by 2n
The stack is bounded to constant size
It is actually O(n log n)
Amortized accounting: pops are prepaid by pushes. No element can be popped twice, so the sum of all inner-loop iterations across the entire pass is at most n.
2In a next-greater pass, when is an element's answer determined?
When it is pushed
✓ At the moment it is popped - the arriving element that pops it is the first larger one to its right
At the end of the pass
When the stack becomes empty
The stack holds unresolved elements in decreasing order. An arrival large enough to pop them is by construction the first value to exceed them - resolution and popping are the same event.
3For 'next greater element to the right', the stack maintains values in which order?
Increasing from bottom to top
✓ Decreasing from bottom to top
Sorted by index only
Heap order
Elements wait for something greater, so anything smaller than the newcomer is resolved and removed; what remains is decreasing. Next-smaller problems invert this to an increasing stack.
4In the histogram problem, what is the appended sentinel bar of height 0 for?
To handle empty input
✓ To force every remaining bar to pop at the end, so ascending histograms still compute their rectangles
To make widths positive
To keep the stack small
Bars are evaluated only when popped. A strictly ascending histogram never pops naturally, so without the sentinel the answer would be 0; height zero is shorter than everything and flushes the stack.
Frequently asked questions
How do I decide between increasing and decreasing stacks?
Name what each element waits for. Waiting for something GREATER means smaller values get popped, leaving a decreasing stack; waiting for something SMALLER leaves an increasing one. Derive it from the pop rule rather than memorizing labels.
Should the stack hold values or indices?
Indices, almost always: they recover values via the array and are required the moment the question involves distance, position, or width. Values-only stacks are a special case that happens to work for pure value queries.
How does the pattern extend to circular arrays?
Simulate two laps: iterate i from 0 to 2n-1 using i mod n for reads, resolving pops throughout, but only pushing indices during the first lap. That gives every element visibility of the wrap-around without duplicating the array.