Week 11 — Monotonic Stack: The Next-Greater Toolkit
Theme. A monotonic stack is the canonical answer to “for each element, find the next/previous greater/smaller.” Mastering it unlocks Trapping Rain Water, Histogram, Stock Span, Sliding Window Maximum, and most “look at neighbors that satisfy a comparison” problems.
Goals
By the end of this week, you should be able to:
- Recognize the pattern in < 30 seconds. “For each
i, find the nearestj > i(orj < i) such thata[j] cmp a[i]” → monotonic stack. - Implement next-greater-element from memory in three flavors: indices, values, circular.
- Derive Largest Rectangle in Histogram from the “for each bar, find the maximal width where it is the minimum” reframing.
- Solve Trapping Rain Water with three independent techniques (two-pointer, prefix max arrays, monotonic stack) and explain the trade-offs.
- Spot the four common bugs: pushing values vs. indices, off-by-one on circular doubling, sentinel handling, strict vs. non-strict comparison.
The 7 Mental Models
| # | Name | Where it bites |
|---|---|---|
| 1 | Indices, not values | You almost always need the position to compute distance/width. Push indices, peek values via a[stack[-1]]. |
| 2 | Maintain invariant on push | “Stack is decreasing” → before pushing a[i], pop while top ≤ a[i]. The popped elements get their “answer” right now. |
| 3 | Resolve at pop, not at push | The element being POPPED is the one whose next-greater is the element being PUSHED. Write that down. |
| 4 | Sentinel zero/inf | For Histogram, append a sentinel 0 to flush the stack; for Trap, the “walls” are implicit via stack ordering. |
| 5 | Circular = double + mod | Iterate 2n indices, i % n to access. Only push real indices the first pass; second pass only pops. |
| 6 | Strict vs ≤ | LC 503 Next Greater II uses STRICT > (equal doesn’t count). LC 84 pops on ≤ to handle equal-height bars correctly. Decide and PROVE. |
| 7 | Each element pushed and popped at most once → O(n) amortized. | Be ready to defend amortized analysis at the whiteboard. |
Problem Table
| # | Problem | LC | Difficulty | Core Skill |
|---|---|---|---|---|
| p51 | Daily Temperatures | 739 | Medium | Indices + “resolve on pop” base case |
| p52 | Next Greater Element I | 496 | Easy | Precompute-then-lookup pattern |
| p53 | Next Greater Element II | 503 | Medium | Circular array via 2n iteration |
| p54 | Largest Rectangle in Histogram | 84 | Hard | “Each bar is the min over a maximal range” reframing |
| p55 | Trapping Rain Water | 42 | Hard | Three techniques: two-pointer, prefix max, monotonic stack |
Daily Schedule
- Mon: p51 Daily Temperatures. Write the template from scratch. Practice tracing on paper.
- Tue: p52 Next Greater Element I. Learn the “precompute on nums2, lookup for nums1” decomposition.
- Wed: p53 Next Greater Element II. Internalize the
2ndoubling trick. - Thu: p54 Largest Rectangle. The hardest reframing of the week. Allow extra time.
- Fri: p55 Trapping Rain Water. Solve it three ways. Time each one.
- Sat: Mixed retrieval — re-solve p51 and p54 cold. Write the next-greater template on a blank page from memory.
- Sun: Buffer + spaced review of Week 10 (Intervals).
Readiness Gate (move to Week 12 only if ALL pass)
- You can write the next-greater-element template in < 3 minutes with zero references.
- You can explain why amortized cost is O(n) and not O(n²).
- You solved Trapping Rain Water THREE ways and can articulate when each is preferable.
- You can derive Histogram from “for each bar, find the maximal width where it’s the minimum” without hints.
- You spotted at least one circular-doubling bug in your own code.
Why This Week Matters
Monotonic stack is one of three patterns (along with two-pointer and binary-search-on-answer) that show up in roughly every other Hard-tier interview at Meta, Google, and the HFT shops. Get it deep into muscle memory now — Week 12 onward (Phase 3) builds on it without re-explaining.