A stack kept sorted by evicting violators: next-greater-element, daily temperatures, and histogram problems in one O(n) pass.
0 of 5 lessons checked off
Introduction
What it is
A monotonic stack maintains its elements in sorted order by popping everything that would violate the order before each push. A DECREASING stack answers next-GREATER questions; an increasing stack answers next-smaller.
The payoff: each pop RESOLVES a waiting element ('your next greater value just arrived'), so one pass answers the question for every index.
Why it matters
The brute force for 'next greater element' scans rightward per index: O(n²). The stack version is O(n) — each index pushes once and pops at most once.
It's the hidden engine of a family of hard-looking problems: daily temperatures, largest rectangle in histogram, trapping rain water, stock span, remove k digits.
How it works
Scan left to right, stack holding INDEXES whose answer is unknown. Before pushing i: while the stack top's value is beaten by nums[i], pop it — nums[i] is its answer.
What remains on the stack at the end never found an answer (−1 / n / 'none', per problem).
The stack always reads sorted top-to-bottom — that's the invariant that makes each comparison decisive.
Where it's used
Stock-span indicators in trading dashboards, skyline/histogram computations in graphics, and compiler parsing of operator precedence all lean on monotonic structures.
In interviews
Next greater element I/II, daily temperatures, largest rectangle in histogram, maximal rectangle, online stock span, remove k digits, sum of subarray minimums.
Analogy: People in a queue each waiting for the first TALLER person to arrive behind them: when a tall person shows up, everyone shorter at the back of the line gets their answer at once and leaves. The line that remains is always height-sorted.
Interactive diagram
Values wait on a decreasing stack; each arrival resolves everything smaller beneath it.
0
1
2
3
4
value
2
1
2
4
3
answer
·
·
·
·
·
Next greater element
Walk left to right keeping a stack of indexes whose answer is unknown. Values on the stack always decrease top-down — hence 'monotonic'.
stack
[]
1 / 10
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Pop = 'your rectangle just closed'; width from the new top.
35 min
Circular arrays and monotonic queues
Double-pass modulo trick; deque variant for window max.
25 min
Operations
Next greater element
Decreasing stack of unresolved indexes; every pop is an answer being written.
0
1
2
3
4
value
2
1
2
4
3
answer
·
·
·
·
·
Next greater element
Walk left to right keeping a stack of indexes whose answer is unknown. Values on the stack always decrease top-down — hence 'monotonic'.
stack
[]
1 / 10
1defnext_greater(nums:list[int])->list[int]:2"""answer[i]=firstvaluerightofigreaterthannums[i],else-1.3O(n):eachindexpushesonce,popsatmostonce."""4answer=[-1]*len(nums)5stack:list[int]=[]# indexes; values decreasing top-down6fori,xinenumerate(nums):7whilestackandnums[stack[-1]]<x:8answer[stack.pop()]=x# x resolves everything smaller9stack.append(i)10returnanswer
Time: O(n) — amortised: ≤ n pushes, ≤ n pops totalSpace: O(n)
Edge cases
Strictly decreasing input: nothing ever pops; all answers −1.
'Greater or equal' variants flip < to <= — read the problem's tie rule.
Distances (daily temperatures): store indexes, answer = i − popped.
Common mistakes
Stacking values instead of indexes, losing the ability to report positions/distances.
Scanning rightward per element 'just to be sure' — the O(n²) the stack deletes.
Largest rectangle in histogram
Increasing stack of bar indexes. Popping a bar means its rectangle just closed: height = the bar, width = between the new top and the current index.
Largest rectangle in histogram
1deflargest_rectangle(heights:list[int])->int:2"""Max rectangle area under the histogram. O(n)/O(n)."""3stack:list[int]=[]# indexes; heights increasing top-down4best=05fori,hinenumerate(heights+[0]):# sentinel 0 flushes the stack6whilestackandheights[stack[-1]]>=h:7height=heights[stack.pop()]8left=stack[-1]ifstackelse-19width=i-left-1# exclusive boundaries on both sides10best=max(best,height*width)11stack.append(i)12returnbest131415if__name__=="__main__":16print(largest_rectangle([2,1,5,6,2,3]))
Time: O(n)Space: O(n)
Edge cases
The appended 0 sentinel forces every bar to pop by the end — no leftover handling.
width uses the element BELOW the popped one as the left wall: bars between were all taller (already popped).
>= vs > on ties: either yields a correct area here, via different pop orders.
Common mistakes
width = i − popped_index (wrong): the rectangle extends LEFT past equal-height bars to the previous shorter bar.
Forgetting the sentinel and separately draining the stack with duplicated width logic (correct but bug-prone).
Complexity analysis
Operation
Best
Average
Worst
Space
Next greater/smaller (all indexes)
O(n)
O(n)
O(n)
O(n)
Largest rectangle in histogram
O(n)
O(n)
O(n)
O(n)
Sliding-window max (monotonic deque)
O(n)
O(n)
O(n)
O(k)
Brute-force next greater
O(n)
O(n²)
O(n²)
O(1)
The amortised argument is the tested line: 'each element pushes once and pops at most once, so the loop-in-a-loop is O(n) total.'
Python implementation
Production-quality code with type hints, validation, and docstrings.
Monotonic deque: sliding-window maximum
1fromcollectionsimportdeque234defwindow_max(nums:list[int],k:int)->list[int]:5"""Maximumofeverylength-kwindow.O(n)/O(k).6Dequeholdsindexes;valuesdecreasefront-to-back;7thefrontisalwaysthecurrentwindow'smaximum."""8ifk<=0:9raiseValueError("k must be positive")10dq:deque[int]=deque()11out:list[int]=[]12fori,xinenumerate(nums):13whiledqandnums[dq[-1]]<=x:# evict dominated values from the back14dq.pop()15dq.append(i)16ifdq[0]<=i-k:# front fell out of the window17dq.popleft()18ifi>=k-1:
What interviewers expect you to know
Recognition signals
'Next/previous greater/smaller element' in any costume (warmer day, taller building, stock span) → monotonic stack.
'Largest rectangle/area under constraints' → increasing stack with pop-closes-rectangle logic.
'Max/min of each sliding window' → monotonic deque.
Design decisions to verbalise
Direction: next-GREATER needs a DECREASING stack (and vice versa) — say which and why before coding.
Ties: < vs <= decides whether equal values resolve each other; the problem's wording decides.
Store indexes when output involves positions, distances, or widths — nearly always.
The complexity defence
When challenged on the nested while: 'total pops across the whole run can't exceed total pushes, which is n — amortised O(n).' Deliver it verbatim.
Common mistakes
Wrong monotonic direction
An increasing stack cannot answer next-greater — nothing would ever pop. Decide direction from what a POP must mean, then keep it consistent.
Values on the stack instead of indexes
Distances (temperatures) and widths (histogram) are index arithmetic. Values-only stacks answer a weaker question than asked.
Histogram width off-by-one
After popping, the left wall is the NEW stack top, not the popped bar: width = i − stack[-1] − 1 (or i when empty). Most failed attempts die exactly here.
Leftovers forgotten
Indexes still stacked at scan's end have no answer — set their −1/n explicitly or use a sentinel to flush them.
Deque evictions from one end only
Window-max needs BOTH rules: dominated-from-back and expired-from-front. Dropping either produces stale maxima.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
Commonly associated with: Amazon, Google, Microsoft
O(rows x cols) time · O(cols) space
Topic quiz
4 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
How do I handle circular arrays (Next Greater Element II)?
Scan the array twice with i % n indexing (or iterate 0..2n−1). Push only during the first pass; the second pass exists purely to resolve leftovers. Same O(n).
Monotonic stack or deque — how do I choose?
One-sided questions ('next greater to the RIGHT') → stack. Range questions with expiry ('max of the last k') → deque, because the front must also evict as the window slides.
Summary & cheat sheet
Key takeaways
Pop-before-push keeps the stack sorted; every pop writes an answer.