Module 8 · Stacks
Practice
Practice~1 min
How to practice this module
Stack problems are matching and history: brackets validate nesting, RPN and the monotonic stack keep recent context. Do valid-parentheses first — the matching discipline repeats everywhere; largest-rectangle is the capstone that sweeps the monotonic stack both directions. Done when all five show Solved in the hub.
Problems
Stacks — work them in order; difficulty ascends.
0/5
solved
- 1Valid ParenthesesEasyBracket matchingWatch for: Push openers, pop on closers; the popped type must match and the stack must end empty
- 2Evaluate Reverse Polish NotationMediumOperand stackWatch for: Pop the last two operands in order — b comes before a for a - b; single-value input returns it directly
- 3Min StackMediumParallel min stackWatch for: Push min(prevMin, value) alongside each element so a pop restores the previous minimum
- 4Daily TemperaturesMediumMonotonic stackWatch for: Store indices, not temperatures; a warmer day only resolves the colder days still waiting
- 5Largest Rectangle in HistogramHardMonotonic stack boundariesWatch for: A bar's rectangle ends at the first smaller bar on each side — pop on a smaller height; a sentinel zero drains the stack
Cheatsheet
Stacks — LIFO for nesting, deferred work, and monotonic candidates.
Smell → pattern
- Valid parentheses / nestingPush open, match close
- Next greater / smaller elementMonotonic stack
- Evaluate expression / calculatorValues + ops stacks
- Histogram / largest rectangleMono heights + widths
- Decode nested stringsStack of frames
Patterns
Match nesting
CoreSmell: Brackets, tags, or nested scopes
Push opening symbols; on close, pop and check the pair. Empty stack at the end ⇔ balanced. A leftover opener is also a fail.
Monotonic stack
SafeSmell: Next greater / smaller to the right (or left)
Keep indices in increasing or decreasing value order. When a new value breaks the mono invariant, pop — each pop answers ‘next’ for that index.
Deferred evaluation
ReachSmell: Infix expression or running calculator
Hold operators until precedence (or a ‘)’) says apply. Two stacks — values and ops — cover most interview expression drills.
Frame stack decode
CarefulSmell: Nested repeats like 3[a2[c]]
Push a frame (count, partial string) when you enter a bracket; pop and multiply when you leave. The stack depth mirrors nesting.
Complexity targets
Linear scan + stack
- Time
- O(n)
- Space
- O(n)
- Note
- Each index push/pop ≤ once
Nested structure walk
- Time
- O(n)
- Space
- O(h)
- Note
- h = nesting depth
Monotonic next-greater
- Time
- O(n)
- Space
- O(n)
- Note
- Amortised one pop per index
| Move | Time | Space | Note |
|---|---|---|---|
| Linear scan + stack | O(n) | O(n) | Each index push/pop ≤ once |
| Nested structure walk | O(n) | O(h) | h = nesting depth |
| Monotonic next-greater | O(n) | O(n) | Amortised one pop per index |
Traps
Peeking an empty stack
Always guard pop/top. Empty means unmatched closer or no candidate yet — both are meaningful states, not just crashes.
Storing values instead of indices
Monotonic ‘next greater’ usually needs indices (for distance or later writes). Storing only values loses where the answer belongs.