Monotonic Stack¶
Also known as: Next Greater Element, Increasing/Decreasing Stack
Keep a stack whose values only ever increase (or only decrease). When a new element violates that order, pop everything it beats — and that pop is the answer for each popped element. Every item is pushed once and popped once, so despite the inner loop it's linear.
Before you start¶
What 'solved properly' looks like
Target: O(n) amortised. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You maintain a stack whose values are strictly increasing or strictly decreasing. When a new value arrives, you pop everything from the stack that violates the monotonic order. For each popped element, the new value is the answer (the "next greater" or "next smaller") that the popped element was waiting for. Because each element is pushed once and popped once, the whole process takes linear time despite the nested-looking loop.
Why it matters: It kills a whole class of O(n²) "look forward until you find something bigger" brute forces, and it's the pattern that most often looks like magic until it clicks. Next greater element, daily temperatures, stock spans, and histogram rectangles all collapse into the same structure.
When to reach for it¶
Reach for it when you see "next greater element", "next smaller element", "previous greater", "how many days until a warmer temperature", stock spans, histogram area, or finding the boundaries where an element is the maximum in its range.
When not to use it
The direction (increasing vs decreasing) must match the question, and choosing wrong produces confident nonsense — decide by asking "what am I waiting for?". If you need arbitrary minimum queries at any time rather than a single forward scan, this isn't the tool; that's a heap or a sparse table.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Next Greater Element I | LeetCode | Easy | 15 mins | teaching |
| 2 | Daily Temperatures | LeetCode | Medium | 20 mins | teaching |
| 3 | Online Stock Span | LeetCode | Medium | 25 mins | consolidation |
| 4 | Next Greater Element II | LeetCode | Medium | 25 mins | consolidation |
| 5 | Largest Rectangle in Histogram | LeetCode | Hard | 45 mins | challenge |
Already know this? Test out.
If you can solve Largest Rectangle in Histogram cleanly in one sitting — tracking the stack of indices and handling the end-of-array flush — you already own this pattern, so move on to the next one. Note that this one is genuinely Hard, and that's the point — it stretches the pattern to its limit. If it doesn't come easily, work the set from the top.
← Stack Matching · Recursion Fundamentals → Back to the roadmap