Run it
The matcher with its stack printed at each step, run over inputs chosen so each of the three failure modes fires once, and a counter-based version that gets one of them wrong.
The solution
O(n) time, O(n) space. Four lines of logic, and each guards a specific failure:
stack.append(ch) records an unresolved opening bracket.
not stack catches a closing bracket with nothing open — ")(".
stack.pop() != pairs[ch] catches a mismatched type — "(]" and "([)]".
return not stack catches unclosed brackets — "(". This is the line people forget, and omitting it makes "(((" valid.
Why a counter does not work
The tempting simplification is to count openings and closings and check they balance. It fails on two of the cases above.
"([)]" has one of each bracket, and every count balances. It is invalid because the nesting crosses, and a counter cannot see order.
")(" also balances by count, and closes before anything is open.
Three separate counters do not help either — the problem is that the most recent unclosed bracket is the one that must close next, and that is last-in-first-out. A stack is not one possible implementation; it is the structure the problem describes.
Saying that explicitly is worth doing in an interview, because it shows you understand why rather than having memorised the solution.
Why a stack and not a counter
With one bracket type, counting works: increment on open, decrement on close, fail if it goes negative or ends non-zero. With several types it does not — "([)]" has balanced counts and is wrong.
A stack captures the thing a counter loses: not just how many are open, but which, and in what order. Nesting is inherently last-in-first-out, which is exactly what a stack is.
The three failure modes
Mismatch. The popped opener does not correspond to the closer. "(]".
Empty stack on a closer. A closer arrived with nothing open. ")(" — and forgetting this check gives an IndexError rather than a False.
Non-empty stack at the end. Openers never closed. "(((" passes every in-loop check and is still unbalanced.
What it generalises to
The same LIFO shape appears in every situation where the most recent unresolved item must be resolved first:
- HTML and XML tag matching —
<div> must close before its enclosing <section>. - Expression evaluation and the shunting-yard algorithm.
- Compiler and interpreter block structure — scopes open and close in nesting order.
- Undo stacks and transaction nesting.
- The call stack itself — the most recent call returns first.
Recognising the shape is what matters. When a problem says "matching", "nesting" or "most recent", a stack is usually the answer.
The three failure modes, traced
"([)]" — the case that separates a stack from a counter:
| Character | Stack before | Action | Result |
|---|
( | [] | Push | [(] |
[ | [(] | Push | [(, [] |
) | [(, [] | Pop gives [, expected ( | Invalid |
"(" — caught by the final check:
| Character | Stack |
|---|
( | [(] |
| End of string | Non-empty → invalid |
")" — caught by the empty-stack guard:
| Character | Stack | Action |
|---|
) | [] | Nothing to pop → invalid |
Walking through those three in an interview covers every branch of the code, which is a concise way to demonstrate the solution is complete.
Edge cases and variations
| Case | Handling |
|---|
| Empty string | Valid — the loop does not run and the stack is empty |
| Non-bracket characters | Ignored by the elif; confirm that is wanted |
| Only opening brackets | Caught by return not stack |
| Only closing brackets | Caught by the not stack guard |
| Very long input | O(n) is fine; the stack can grow to n |
| Single bracket type | A counter would suffice — worth mentioning |
That last row is a good observation to volunteer: with only one bracket type, a counter works, and the stack is needed precisely because there are several types whose nesting must be tracked.
The follow-ups
"What if the input can contain other characters?" The code already ignores them. Confirm whether that is intended, or whether they should be an error.
"Return the position of the first error." Track the index in the loop and return it instead of False. This is what an editor's bracket matcher does.
"What if brackets can be wildcards?" The "valid parenthesis string with *" variant, where * can be (, ) or empty. The stack approach no longer suffices; the standard solution tracks a range of possible open counts, or uses two counters for the minimum and maximum.
"Find the longest valid substring." A different problem — stack of indices, or dynamic programming. Considerably harder, and a common escalation.
"What if brackets can be removed to make it valid?" Minimum removals: count unmatched brackets in one pass, which is the counter approach applied correctly to a different question.
Recap in one screen
- Push openings; on a closing bracket, pop and check the type matches.
- Four guards: push, empty-stack check, type check, and the final "stack must be empty".
- A counter cannot solve it, because
"([)]" balances numerically and nests wrongly — order matters. - O(n) time and O(n) space; the stack can reach the length of the input.
- Same shape as tag matching, expression parsing and scope tracking — "most recent first" means stack.