BeginnerStack
Matching brackets with a stack
Push every opening bracket; on a closing one, the top of the stack must be its partner. Last opened, first closed.
The idea
Brackets close in the reverse order they open: the most recently opened must close first. That “last in, first out” order is exactly what a stack gives you.
At the end the stack must be empty, or something was opened and never closed.
Worked example
“( [ ] )” and “( ]”
- ( → push → [(] [ → push → [(, [] ] → top is [ ✓ pop ) → top is ( ✓ pop → empty → valid
- ( → push ] → top is ( but needs [ → invalid
In code (Python)
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stackO(n) time, O(n) space.
How to spot it
- Nested structure: brackets, tags, “undo the most recent”, evaluating expressions.
Common mistakes
- Popping from an empty stack on input like “)”.
- Forgetting the final emptiness check, so “((” passes.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →