How Do You Solve the Valid Parentheses Problem?
Learn how to solve the valid parentheses problem with a stack, its edge cases, and how to answer this interview question well.
Expected Interview Answer
The valid parentheses problem is solved with a stack: push every opening bracket you encounter, and on every closing bracket, check that the stack's top is the matching opener and pop it, declaring the string invalid if it mismatches or the stack is empty; the string is valid only if the stack is empty at the end, giving O(n) time and O(n) space.
A stack fits this problem because bracket matching is inherently last-in-first-out: the most recently opened bracket must be the next one closed. As you scan left to right, opening brackets go onto the stack unconditionally, while a closing bracket must immediately match whatever is currently on top — if the stack is empty when a closer arrives, or the top doesn't match the closer's type, the string is invalid and you can short-circuit immediately. After the scan, an empty stack means every opener found its matching closer in the correct order, while a non-empty stack means some openers were never closed. This same push/pop-on-match pattern generalizes directly to any nested, well-formed structure problem, such as validating XML tags or balancing multiple bracket types simultaneously.
- O(n) time with a single left-to-right scan
- O(n) space in the worst case (all openers, no closers)
- Naturally supports multiple bracket types with one map lookup
- Fails fast — can return false the instant a mismatch is found
AI Mentor Explanation
A scorer tracking nested overturned appeals uses a stack: every time an appeal is raised, it goes on top of the pending pile, and every time an umpire's decision comes in, it must resolve the appeal currently on top of the pile, not some earlier one buried underneath. If a decision arrives when the pile is empty, or it tries to resolve the wrong appeal, the review sequence is broken. Only when every raised appeal has been resolved in the correct nested order does the pile end up empty, meaning the whole sequence of appeals was valid. This last-raised-first-resolved rule is exactly why a stack, not a queue, models the appeals correctly.
Step-by-Step Explanation
Step 1
Initialize an empty stack
Also prepare a map from each closing bracket to its matching opening bracket.
Step 2
Push on open brackets
Scan left to right; whenever you see (, [, or {, push it onto the stack.
Step 3
Pop and match on close brackets
On a closing bracket, if the stack is empty or the top does not match, return false immediately.
Step 4
Check the stack is empty at the end
After the scan, the string is valid only if the stack has no leftover unmatched openers.
What Interviewer Expects
- Identify a stack as the right structure due to LIFO nesting behavior
- Handle the empty-stack-on-closer edge case explicitly
- Handle a non-empty stack at the end as an invalid result
- State the final complexity as O(n) time and O(n) space
Common Mistakes
- Using a counter of open vs close brackets instead of a stack, which fails on mixed bracket types like "([)]"
- Forgetting to check for an empty stack before popping on a closing bracket
- Forgetting to verify the stack is empty at the very end of the scan
- Not short-circuiting on the first mismatch, doing unnecessary extra work
Best Answer (HR Friendly)
“I use a stack because closing brackets always need to match the most recently opened one, not an older one. I push every opening bracket I see, and on a closing bracket I check it against whatever is on top of the stack — if it doesn't match, or there's nothing there, I know the string is invalid right away. If I finish the scan and the stack is empty, everything matched up correctly.”
Code Example
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0Follow-up Questions
- How would you extend this to also validate custom tag pairs like HTML tags?
- How would you find the longest valid parentheses substring instead of just checking validity?
- What is the minimum number of insertions to make an invalid string valid?
- How would you solve this problem with O(1) extra space?
MCQ Practice
1. Which data structure correctly models nested bracket matching?
Brackets close in last-in-first-out order, which is exactly what a stack enforces via push and pop.
2. What should happen when a closing bracket is encountered but the stack is empty?
An empty stack on a closer means there is no matching opener, so the string is immediately invalid.
3. Why does a simple open/close counter fail on a string like "([)]"?
A counter would see equal opens and closes and call it valid, but the bracket types close out of proper nested order.
Flash Cards
What data structure solves valid parentheses? — A stack, because bracket closing follows last-in-first-out order.
What do you push onto the stack? — Every opening bracket encountered while scanning left to right.
When is the string considered valid? — When every closing bracket matched the stack top correctly and the stack is empty at the end.
What is the time and space complexity? — O(n) time for a single scan, O(n) space in the worst case for the stack.