Originally published on LeetCopilot Blog
Keep elements in sorted order so the top tells you the next smaller or greater value. Sound confusing? Here's the visual breakdown.
Monotonic stacks sound intimidating until you see the pattern: keep elements in sorted order so the top tells you the next smaller or next greater value. This guide keeps it visual, repeatable, and interview-focused.
TL;DR
- Monotonic stacks maintain sorted order (increasing or decreasing) to answer nearest-greater/smaller queries in O(n).
- Interviews care because many array problems collapse to this pattern once you see the next/previous boundary idea.
- Core steps: choose direction, define what the stack stores, pop while breaking the order, record answers as you pop.
- Beginners misunderstand which order to keep and when to pop, leading to wrong boundaries or infinite loops.
- You'll learn invariants, a table-driven walk-through, a TypeScript snippet, and a pitfalls checklist tailored to practice sessions.
Beginner-Friendly Explanations
What a Monotonic Stack Guarantees
A monotone decreasing stack stores values where each new item is smaller; the top is the nearest smaller to the right. A monotone increasing stack reverses this for nearest greater. The invariant is the guarantee you defend every iteration.
Why Direction Matters
You push while scanning left → right to find the next boundary; you scan right → left for previous boundaries. Decide up front to avoid flipping conditions later.
Step-by-Step Learning Guidance
1) Define the Question
- Are you searching for next greater, previous smaller, or both?
- Do you need indices, values, or distances? Write it explicitly.
2) Choose Stack Type and Scan Direction
- Next greater element → monotone decreasing stack, scan left → right.
- Previous smaller element → monotone increasing stack, scan left → right.
- Largest rectangle in histogram → monotone increasing stack with a sentinel 0 at the end.
3) State the Invariant Out Loud
"The stack holds indices with heights in increasing order; when a lower bar appears, I pop until the invariant holds." This makes mistakes obvious during a mock interview routine.
4) Pop, Record, Push
- Pop while the next element breaks the order.
- Record answers for every item you pop because the current element is its nearest boundary.
- Push the current index to keep the invariant for future iterations.
5) Close With a Sweep
If answers need a boundary on both sides (e.g., widths), flush remaining stack with a sentinel value so every bar gets processed.
Visualizable Example: Histogram Widths
Input heights: [2,1,5,6,2,3]
Stack holds indices with increasing heights
[0] -> height 2
[1] -> pop 0 (because 1 < 2), push 1
[2] -> push 2 (5 > 1)
[3] -> push 3 (6 > 5)
[4] -> pop 3, pop 2 (2 < 5), compute widths for bars 3 and 2
[5] -> push 5, sentinel 0 pops remaining
Each pop knows its left and right limits, giving the max area in O(n). The sliding window visualizer can mirror this trace to cement intuition.
Practical Preparation Strategies
Build a Tiny Decision Table
- Need next greater? Decreasing stack, scan left → right.
- Need previous smaller? Increasing stack, scan left → right.
- Need nearest boundary both sides? Two passes or store both during pops. Keep this table in your practice roadmap notes.
Rehearse With Micro-Inputs
Practice on arrays of length 1–4 to see each pop/push. Tools like LeetCopilot can overlay the stack state while you narrate, catching missed pops.
Use Sentinels Intentionally
Add a 0 or Infinity sentinel to force the final pops. Explain why you're adding it—it signals confidence to interviewers.
Common Mistakes to Avoid
Forgetting to Record Answers on Pop
If you push before recording, you lose the "nearest" relation and end up with default values.
Mixing Value vs Index Stacks
Storing values when you need distances makes width calculations impossible. Default to storing indices unless the problem says otherwise.
Popping With the Wrong Comparison
Using <= instead of < changes tie handling. Decide how duplicates should behave and code that explicitly.
Code Example: Next Greater Element (Left to Right)
function nextGreaterElements(nums: number[]): number[] {
const res = Array(nums.length).fill(-1);
const stack: number[] = []; // holds indices, heights decreasing
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
const idx = stack.pop()!;
res[idx] = nums[i];
}
stack.push(i);
}
return res;
}
We store indices so we can fill results in place. The while loop enforces the decreasing invariant; every pop finds its next greater element.
FAQ
How do I know if I need an increasing or decreasing stack?
Ask whether the current element should remove smaller or larger past elements. Removing smaller → decreasing stack; removing larger → increasing stack.
What should I practice before monotonic stacks?
Get comfortable with arrays, loops, and basic stack operations. Then solve a few "next greater element" variants before tackling histogram area.
Is the monotonic stack pattern important for interviews?
Yes, it's a go-to technique for next/previous boundary problems and shows up in medium/hard LeetCode questions.
How do I debug when my stack never empties?
Log each push/pop and assert the invariant after every iteration. An unpopped stack usually means you forgot a sentinel or used the wrong comparison.
Can I use this for circular arrays?
Yes—iterate twice or use modulo on indices so each element gets a chance to be the "next" for earlier items.
Conclusion
Monotonic stacks are less about memorizing formulas and more about defending an invariant: sorted order that makes boundaries obvious. With small input drills, sentinels, and explicit pop-record-push steps, beginners can turn a confusing pattern into a confident interview tool. Structured practice—and occasional guided traces from tools like LeetCopilot—keeps the pattern fresh without guesswork.
If you're looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.
Top comments (0)