roadmap/Stack

Topic 4 / 16

Stack

EasyLinear~3 days
Easy to grasp
progress0 / 13 solved

LIFO structure for matching, undo operations, and monotonic problems.

Unlocks
Trees →
Concept

A stack is a LIFO (Last-In-First-Out) structure. Push to add, pop to remove from the top. It models 'most recent unresolved state' — perfect for matching open/close pairs, undo history, and processing nested structures. Monotonic stacks (elements in sorted order) efficiently find next-greater or next-smaller elements.

When to use this pattern
  • ◆Matching brackets, parentheses, or tags
  • ◆Undo/redo or history navigation
  • ◆Expression evaluation (infix, postfix)
  • ◆Next greater/smaller element problems
  • ◆DFS iteratively (instead of recursive call stack)
Common patterns
Matching pairs
Push open brackets; pop and verify on close brackets.
Monotonic stack (increasing)
Pop elements smaller than current — find next greater element.
Monotonic stack (decreasing)
Pop elements larger than current — find next smaller element.
Min stack
Track running minimum with an auxiliary stack.
Visual walkthrough
Monotonic Stack
Daily Temperatures
PUSH
temperatures[]
73
0
74
1
75
2
71
3
69
4
72
5
76
6
73
7
stack (indices)
empty
Start. Stack holds indices of "unresolved" temperatures.
We want: for each day, how many days until a warmer day?
step 1/17
Brute force → optimal thinking
Brute force
For each element, scan forward to find the next greater → O(n²).
Observation
Once we find a greater element, everything smaller we passed is resolved.
Optimization
Maintain a monotonically decreasing stack. When a larger element arrives, pop and assign answers to everything it's greater than.
Final complexity
O(n) — each element pushed and popped exactly once.
Quick Recall Check

What ordering property does a stack enforce?

In a monotonic decreasing stack, what happens when a larger element arrives?

What is the time complexity of finding the next greater element using a monotonic stack?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Sliding Window
next
Binary Search
→
Progress is saved on this device