Valid Parentheses
Given a string of ()[]{}, decide whether every bracket is closed by the correct type in the correct order.
Intuition
Brackets nest last-opened, first-closed — exactly a stack. Push each opener; when a closer arrives, the bracket on top must be its match. If not (or the stack is empty), it is invalid.
A stack is the answer whenever the structure is nested rather than merely counted — the most recent thing opened must be the first thing closed. The tell is that a simple counter breaks: ([)] keeps both counts balanced yet is invalid. Once you need to know which bracket is innermost, you need LIFO. The same reflex drives expression parsing, path simplification, and nested decoding.
Approach
Repeatedly stripping pairs is slow
One correct idea is to keep deleting adjacent matched pairs — (), [], {} — until the string stops changing; if you end with nothing, it was valid. It works but each deletion rewrites the string, giving O(n²). The structure of the problem points at a data structure that handles nesting in linear time.
Brackets nest last-in, first-out — that's a stack
Valid brackets close in the reverse order they opened: the most recently opened bracket must be the next one closed. That 'most recent unmatched thing' is exactly what a stack tracks. Push every opening bracket; the top of the stack is always the only bracket a closer is allowed to match.
Match each closer against the top
Map each closing bracket to its required opener. On an opener, push it. On a closer, it's invalid if the stack is empty (nothing to close) or if the popped top isn't its matching opener (wrong type). After the scan, the string is valid only if the stack is empty — a leftover opener means something was never closed. One pass, O(n) time, O(n) space for the stack.
Solution & live demo
Common pitfalls
Counting brackets instead of stacking them
open_count = 0
for ch in s:
if ch in "([{": open_count += 1
else: open_count -= 1
return open_count == 0stack = []
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)Counting accepts ([)] — three types balance numerically while crossing each other. Only a stack records the order of what's open, which is what nesting actually means.
Popping an empty stack
if stack.pop() != pairs[ch]:
return Falseif not stack or stack.pop() != pairs[ch]:
return FalseA string that begins with a closer, like "]", pops nothing and raises IndexError. The emptiness check must short-circuit before the pop.
Returning True without checking for leftovers
for ch in s:
...
return Truefor ch in s:
...
return not stack"(((" never triggers a mismatch because it never closes anything — the loop finishes cleanly with three items still stacked. Valid means every opener was also closed, so the stack has to be empty at the end.
Edge cases
The popped opener ( does not equal the expected [, so it returns false.
Popping an empty stack is caught by the not stack check, returning false.
The loop ends with a non-empty stack, so not stack is false — correctly invalid.