When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Nested structure
- Matching delimiters
- Nearest prior candidate
When another approach fits better
- The earliest pending item must be handled first
- Only aggregate counts matter and item order is irrelevant
How it works#
Repeatedly rescan prior tokens or search backward for the next unresolved match.
Define what one stack entry represents.
Push only unresolved state.
On a resolving token, validate the top before popping and decide what an empty stack means.
InvariantThe stack contains unresolved items from the processed prefix in exactly the order they may be closed or dominated.
Example and template#
Valid Parentheses
Store unresolved opening delimiters and reject mismatches immediately.
Open the full problem brief- Read ( [
stack: (, [Both open scopes remain unresolved.
- Read ]
stack: (Only the top scope can close next.
stack = empty
for token in input:
if token opens work: push token
else:
if stack empty or top mismatches: fail
pop
return stack is empty- Time
- O(n)
- Space
- O(n) worst case
- Assumptions
- Each item is pushed and popped at most once.
Pitfalls#
Common wrong approaches
Equal counts do not preserve nesting order.
Malformed leading closers cause invalid access instead of a clean failure.
Edge cases
- Empty input
- Leading closer
- Unclosed opener
- Multiple token families
Interview narration
- “Only the most recent unresolved opener can match this closer.”
- “My stack is exactly the unmatched prefix.”
- “Any mismatch fails immediately; an empty stack at the end proves all scopes closed.”
Practice#
Valid Parentheses
Store unresolved opening delimiters and reject mismatches immediately.
Practice this problemEvaluate a sequence of undoable editor operations with nested begin/end transactions.
Reveal the pattern decision
Use a stack for the active transaction frames; a queue would violate last-opened-first-closed order.
Transfer problem
Simplify a filesystem path containing current and parent-directory segments.
Checkpoint: Define which segments push, pop, or do nothing and how root underflow behaves.
Follow-up variations
- Return the first error position
- Design a min-tracking stack with O(1) minimum queries
Error-log prompts
- What did the top mean?
- Did every pop have an empty-state guard?