Learn stack interview patterns with animated bracket matching, reverse Polish notation and monotonic stack examples. Explore explanations and Python solutions.
The pattern
Stack: the most recent unfinished thing comes first
A stack only lets you touch its top: push onto it, pop off it. That sounds limiting, but many problems only ever need the latest item: the bracket opened last, the two values computed last, the days still waiting for an answer. Each push and pop is O(1), and an item is pushed and popped once, so most stack solutions are O(n).
1Last in, first out
In “{ [ ( ) ] }” the bracket that closes next is always the one opened most recently. A stack keeps exactly that order: push when something opens, and the top is what must close first.
2The stack remembers unfinished work
In “3 4 + 2 ×”, numbers wait on the stack until an operator needs them. The operator takes the two most recent values and pushes its result back, ready for the next operator.
3Monotonic stack: one item answers many
Cool days wait on a stack, warmest at the bottom. When a warmer day arrives it answers every cooler day on top at once, then waits itself. Each day is pushed and popped once: O(n).
How to spot it
- Nesting: brackets, tags, folders, function calls. The innermost finishes first.
- “Undo the last step”: backtracking builds a stack and pops after each try.
- “Next greater / smaller element”, “how far until something bigger”: a monotonic stack.
- Expressions and calculators: values wait until an operator uses them.
Plain stack vs monotonic stack
- Plain: Valid Parentheses, Min Stack, RPN, Generate Parentheses. New to stacks? See the Stack and Queue page first.
- Monotonic: the stack is kept sorted by popping anything a new item makes useless. Daily Temperatures, Car Fleet and Largest Rectangle. It's the same “drop what can never win” idea as the deque in Sliding Window Maximum.
Python: stack = [], stack.append(x), stack.pop(), stack[-1] (top)
NeetCode 150 · Stack
All 7 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Valid Parentheses
EasyBlind 75Given a string of the brackets ( ) [ ] { }, return true if every opening bracket is closed by the same kind of bracket, in the right order.
s = "{[()]}()"
s
stack (bottom → top)
variables
- open, not yet closed
- 0
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 8 ops
- Brute force
- 14 ops
On a bigger input (200 brackets, nested):
- Pattern
- 200 ops
- Brute force
- 10,100 ops
Keep deleting adjacent pairs like “()” until none are left, then check the string is empty. Deeply nested input needs a pass for every level: O(n²).
“ops” counts basic steps: lookups, inserts, comparisons, array reads. On tiny inputs brute force can even win, because it may stumble on the answer early; as n grows, the gap opens up.
How it works: Valid Parentheses
Step by step
- Current bracket
- Open, on the stack
- Matched pair
- The problem
Press Start or Step: the step the animation is on lights up below.
- 1
Empty stack
Nothing is open yet.
stack = [] - 2
Opening bracket → push
It waits until its partner arrives.
stack.append(c) - 3
Closing bracket matches the top → pop
That pair is complete.
if stack and stack[-1] == pairs[c]: stack.pop() - 4
Wrong kind, or nothing open → false
The closing bracket has no partner.
return False - 5
End with brackets still open → false
Some were never closed.
return not stack - 6
End with an empty stack → true
Every bracket was closed in order.
return not stack
The bracket that must close next is always the one opened most recently. “Most recent first” is exactly what a stack gives you: push when a bracket opens, and when one closes, it must match the top.
It's invalid if a closing bracket doesn't match the top, if the stack is empty when one closes, or if anything is still open at the end.
Spot it in an interview
- Nested structure: brackets, tags, function calls. The innermost thing finishes first.
- Whenever you need “the most recent unfinished item”, use a stack.
Each bracket is pushed and popped at most once; in the worst case all of them are open at once.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.