Valid Parentheses
Asked at Google, Meta, Amazon, Microsoft, Walmart
Problem
Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid. An input string is valid if brackets are closed in the correct order. This problem tests your understanding of the stack data structure.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Walmart | Easy | View all Walmart questions → |
How to Think About It
A stack is the natural data structure — push opening brackets, pop on closing brackets. The most recent unmatched opening bracket is always on top.
The key check: when you see a closing bracket, is the stack non-empty AND does the top match? If not, return false immediately.
Why stack works: brackets must close in LIFO order. The last opened bracket must be the first closed. That's exactly how a stack behaves.
Visual walkthrough for "({[]})":
( → push. Stack: [(]
{ → push. Stack: [(, {]
[ → push. Stack: [(, {, []
] → top is [, matches! Pop. Stack: [(, {]
} → top is {, matches! Pop. Stack: [(]
) → top is (, matches! Pop. Stack: []
Stack empty → valid!
Visual walkthrough for "(]":
( → push. Stack: [(]
] → top is (, doesn't match ]. Return false.
Edge cases: odd-length strings are always invalid (early exit). Empty string is valid. Single bracket is invalid.
Optimal Approach
Step 1: Create a mapping of closing to opening brackets: {")":"(", "}":"{", "]":"["}.
Step 2: Iterate through the string.
Step 3: If character is an opening bracket, push it onto the stack.
Step 4: If character is a closing bracket:
- If stack is empty → return
false(no matching opener) - If stack top doesn't match → return
false(wrong type) - Otherwise pop the matching opener
Step 5: After processing all characters, stack must be empty (all openers were closed).
Time: O(n). Space: O(n) for the stack.
What Trips People Up in Real Interviews
Using a counter instead of a stack. A counter works for one type of bracket, but with multiple types, you need a stack to match the correct closing bracket.
Pushing closing brackets onto the stack. Only push opening brackets. When you see a closing bracket, check if it matches the top of the stack.
Forgetting to check if the stack is empty before popping. If the stack is empty when you see a closing bracket, it's invalid (no matching opener).
Not checking if the stack is empty at the end. If the stack has unmatched openers, it's invalid.
Replacing pairs iteratively instead of using a stack. Replacing "()" with "" repeatedly is O(n²) worst case and doesn't generalize to multiple bracket types. A stack handles all types in O(n).
Solution Code
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in mapping:
if not stack or stack[-1] != mapping[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stackFrequently Asked Questions
What is the Valid Parentheses problem?
Given a string containing just the characters (, ), `{, }`, [ and ], determine if the input string is valid. An input string is valid if brackets are closed in the correct order. This problem tests your understanding of the stack data structure.
How do you solve Valid Parentheses?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Valid Parentheses?
Valid Parentheses is asked at Google, Meta, Amazon, Microsoft, Walmart. It is a easy difficulty problem.
What are common mistakes on Valid Parentheses?
- Using a counter instead of a stack. A counter works for one type of bracket, but with multiple types, you need a stack to match the correct closing bracket.
- Pushing closing brackets onto the stack. Only push opening brackets. When you see a closing bracket, check if it matches the top of the stack.
- Forgetting to check if the stack is empty before popping. If the stack is empty when you see a closing bracket, it's invalid (no matching opener).
- Not checking if the stack is empty at the end. If the stack has unmatched openers, it's invalid.
- Replacing pairs iteratively instead of using a stack. Replacing "()" with "" repeatedly is `O(n²)` worst case and doesn't generalize to multiple bracket types. A stack handles all types in `O(n)`.