Stack Matching¶
Also known as: Bracket Matching, LIFO Validation, Stack of Pending Work
Push things that are waiting to be resolved; pop when the thing that resolves them arrives. The stack is a memory of "what's still open," and the last thing opened is always the first thing that must close.
Before you start¶
- Comfortable with basic array/list push and pop operations in your language.
What 'solved properly' looks like
Target: O(n) time, O(n) space. 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 of pending items. Only opening items are pushed onto the stack. When a closing item arrives, it must match the item on top of the stack — if it does, you pop; if it doesn't (or the stack is empty), the input is invalid immediately. This captures the LIFO (last-in, first-out) nature of nesting: the most recently opened thing is always the one that must close next.
Why it matters: Nesting is everywhere — brackets, tags, function calls, undo history, file paths — and the moment a problem has nesting, a stack is almost always the answer. Mastering this simple push-pop discipline unlocks expression evaluation, syntax validation, and the monotonic stack that follows in the next pattern.
When to reach for it¶
Reach for it when you see nested structure, brackets or parentheses that must be balanced, tags that open and close, undoing the last action, evaluating an expression in postfix notation, or simplifying a path with ".." segments.
When not to use it
If the order you need is first-in-first-out, you want a queue, not a stack — and getting this backwards is the classic error. Also: if there's only one type of bracket and you only need a yes/no answer, a simple counter does the job in O(1) space; the stack earns its memory when there are multiple bracket types or you need the pending items themselves.
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 | Valid Parentheses | LeetCode | Easy | 15 mins | teaching |
| 2 | Remove All Adjacent Duplicates In String | LeetCode | Easy | 15 mins | teaching |
| 3 | Min Stack | LeetCode | Medium | 20 mins | consolidation |
| 4 | Evaluate Reverse Polish Notation | LeetCode | Medium | 25 mins | consolidation |
| 5 | Simplify Path | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Simplify Path cleanly in one sitting — handling the ".." and "." segments with a stack — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.