Monotonic Stack
What is this?
Imagine standing in a line, each person waiting for the first taller person to walk by. A monotonic stack keeps that waiting line tidy by holding only the people who could still be "answered" — the moment a taller person arrives, everyone shorter who was waiting gets their answer at once and leaves the line. Because each person joins and leaves only once, a problem that looks like it needs you to compare everyone with everyone else finishes in a single quick pass.
💡 Fun fact: The "stock span" feature on finance dashboards — how many days until a higher price — is computed with this exact trick, which is why it stays fast even over years of daily data.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Keep a stack whose values stay sorted (always increasing or always decreasing). When a new element would break that order, you pop every element it dominates — and that pop is exactly the moment each popped element finds its answer. Each element is pushed and popped once, so problems that look O(n²) collapse to O(n).
The leap this chapter teaches
Many sequence problems ask, for each element, "what's the next/previous element that's bigger (or smaller)?" The brute force re-scans forward for every element — O(n²). A monotonic stack avoids the re-scan by holding only the elements that are still waiting for an answer, in sorted order. The instant a "dominator" arrives, it resolves all the waiters it beats in one sweep.
The magic is amortized: an element is pushed once and popped at most once, so the total work across the whole scan is O(n) even though any single step might pop many items.
The two shapes
- Decreasing stack → answers "next greater" questions. You pop when the incoming element is larger.
- Increasing stack → answers "next smaller" / dominance questions.
The choice of increasing vs decreasing, and whether you store values or indices, is the entire design decision.
The three problems
Daily Temperatures — next greater element
For each day, how many days until a warmer one? Keep a decreasing stack of day indices. When today beats the day on top, pop it and record today − that_day. → O(n) / O(n).
Buildings With Ocean View — visibility / dominance
Ocean is to the right; a building has a view iff every building to its right is shorter. Equivalent to a right-to-left scan keeping a running max (a monotonic stack in disguise): a building survives iff it's taller than everything seen so far on its right. → O(n) / O(n).
Trapping Rain Water — settle water in layers
Walk the bars with a decreasing stack of indices. When a taller bar arrives, it closes a dip: pop the floor, and the water sealed in is a flat slab — width = gap between the new wall and the wall under the floor, height = min(left, right) − floor. → O(n) / O(n) (or two-pointer for O(1) space).
The cross-cutting skill: decide the four knobs
| Knob | Question | Example answer |
|---|---|---|
| Direction | left→right or right→left? | Daily Temps: left→right |
| Monotonic order | increasing or decreasing? | next-greater → decreasing |
| Store | values or indices? | indices when you need distances |
| Pop action | what gets recorded on a pop? | the gap, the area, the survivor |
Every monotonic-stack solution is the same skeleton: while the stack's top is dominated by the current element, pop it and record its answer; then push the current element. Pick the four knobs and the loop writes itself.
📓 Draw it yourself
- Resolution sweep. For Daily Temperatures, draw the bars and the index-stack beside them; when a tall bar arrives, draw arrows popping every shorter waiting bar. Seeing one arrival resolve several waiters is the O(n) insight.
- Water slabs. For Trapping Rain Water, draw a cross-section and shade each flat slab of water the moment a taller-right wall seals it. Label width and bounded height.
Snap photos and embed them with the /host-diagrams skill.
Complexity at a glance
| Problem | Time | Space |
|---|---|---|
| Daily Temperatures | O(n) | O(n) |
| Buildings With Ocean View | O(n) | O(n) |
| Trapping Rain Water | O(n) | O(n) (O(1) via two pointers) |
Key takeaways
- Keep the stack sorted; pop on a dominator. That pop is when a waiting element gets its answer.
- It's amortized O(n): each element is pushed once and popped once, no matter how many pops a single step triggers.
- Decreasing stack → next greater; increasing stack → next smaller. Choose direction, order, and value-vs-index up front.
- Recognize the trigger: "for each element, find the nearest bigger/smaller one" almost always means a monotonic stack.
- Why this chapter matters: it's the highest-leverage stack pattern in interviews — turning O(n²) scans into one linear pass — and shows up across time-series, skyline, and capacity problems.
Order: Daily Temperatures (the template) → Buildings With Ocean View → Trapping Rain Water (the hardest, settling water in layers).