DSA & Algorithms
Part 7 of 21 · DSA Interview PatternsStack & Monotonic Stack — Next Greater, Histograms & Parsing
Monotonic stacks for next-greater/smaller, histogram areas, and expression parsing.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Each index wants its next greater or smaller neighbor
Prefer
A monotone stack, each index once
The stack keeps candidates in order. When the new value beats the top, that top has found its answer.
- Next greater pops while the top is smaller.
- Histogram width is the gap between the new bar and the bar still on the stack.
- A sentinel zero closes the last rectangle.
Alternative
Scan the rest of the array for every index
The naive next-greater scan is quadratic and hides the stack.
- Pushing values when you needed indexes.
- Strict versus non-strict compare on duplicates.
- A queue for nested parentheses.
Pop the answers, then push
The stack is decreasing or increasing on purpose. The top is the neighbor you might resolve.
- 1
Scan left to right
The new index is the candidate answer for older indexes. - 2
Pop while the top loses
Record next greater, or a histogram width, then discard. - 3
Push the index
Values alone cannot answer distance or width.
Overview
Monotonic stacks for next-greater/smaller, histogram areas, and expression parsing.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use a stack for LIFO nesting (parens, path), and a monotonic stack when each element needs the next greater/smaller to the left or right.
Recognition cues
- next greater element / daily temperatures
- largest rectangle in histogram
- remove k digits / asteroid collision
- valid parentheses
Mental model
Decisions
- 1
1. Scan left to right
- next2. Is the top worse?
- ?
2. Is the top worse?
- yes3. Pop and record
- no4. Push index i
- 3
3. Pop and record
- next2. Is the top worse?
- 4
4. Push index i
Lesson map
Stack & Monotonic Stack — Next Greater, Histograms & Parsing
Monotonic stacks for next-greater/smaller, histogram areas, and expression parsing.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB i["1. Scan left to right"] c["2. Is the top worse?"] pop["3. Pop and record"] push["4. Push index i"] i -->|1. Scan left to right| c c -->|yes| pop c -->|no| push pop -->|3. Pop and record| c
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Each index pushed/popped at most once → O(n) time, O(n) space.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Valid Parentheses
- Daily Temperatures
- Next Greater Element I
- Largest Rectangle in Histogram
- Asteroid Collision
- Remove K Digits
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Why monotonic?
Answer
Maintain increasing/decreasing so the top is the candidate neighbor.
Next greater template?
Answer
While the stack top < current, pop and set answer to current.
Histogram trick?
Answer
For each bar, find nearest smaller left and right; area = h * width.
Parens only stack?
Answer
Yes - push openers; mismatch or leftover means invalid.
Asteroid collision?
Answer
Stack of survivors; resolve opposing directions at top.
Space?
Answer
O(n) worst case when array is strictly mono already.