Valid Parentheses
Check bracket matching with a stack — the canonical example of last-in-first-out logic
Problem Statement
Given a string containing only (, ), {, }, [ and ], determine whether it is valid. A string is valid when:
- Every open bracket is closed by the same type of bracket.
- Brackets close in the correct order.
- Every close bracket has a matching open bracket.
Input: "()" → true
Input: "()[]{}" → true
Input: "(]" → false (wrong type)
Input: "([)]" → false (wrong order)
Input: "{[]}" → true
Input: "(" → false (never closed)Intuition
Counting brackets is not enough. "([)]" has one of each and is still invalid — the order is wrong. What matters is nesting.
The key insight
The most recently opened bracket must be the first one closed. That is exactly last in, first out — the definition of a stack.
Push every opening bracket. On a closing bracket, look at the top of the stack: if it is the matching opener, pop it; otherwise the string is invalid.
Walk through "([)]":
'(' → push stack: [ ( ]
'[' → push stack: [ (, [ ]
')' → top is '[', which does not match ')' → INVALIDThe stack catches the ordering error that counting never would.
Real-world analogy
A stack of plates. You place plates on top and take them off the top. Trying to pull out the third plate from the middle breaks the stack — just as "([)]" tries to close the ( while [ is still open.
Watch it run
Approach
Build a map from closing to opening bracket
{')': '(', ']': '[', '}': '{'}. Keying by the closer makes the lookup direct and doubles as an "is this a closer?" test.
On a closing bracket, check the top
If the stack is empty, or its top is not the matching opener, return false. Otherwise pop.
At the end, the stack must be empty
A non-empty stack means openers were never closed — "(((" fails here, not inside the loop.
Both failure checks are required
"(" passes every check inside the loop and is still invalid. ")" fails the empty-stack check inside the loop. You need both the mid-loop mismatch test and the final emptiness test — dropping either one accepts invalid strings.
Solution
def is_valid(s: str) -> bool:
"""True if every bracket is matched and correctly nested."""
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for char in s:
if char in pairs:
# A closing bracket: the top must be its partner.
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stack # leftovers mean unclosed bracketsWhy the TypeScript version needs no empty check
Array.prototype.pop() on an empty array returns undefined, which never equals any bracket character, so the mismatch branch fires naturally. Python's list.pop() raises IndexError instead, which is why not stack has to be tested first. Same logic, different language behaviour.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — one pass; each character is pushed and popped at most once.
- Space — worst case
O(n)when the string is all openers, like"(((((". Best caseO(1)for something like"()()()"where the stack never holds more than one item.
Edge Cases
Related Problems
- Min Stack — extending a stack with an extra invariant
- Evaluate Reverse Polish Notation — a stack holding operands rather than symbols
- Simplify Path — a stack of path components, where
..is a pop