Valid Parentheses
Decide whether a string of (), [], and {} brackets is properly matched and nested. The classic first problem for using a stack. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s made only of the characters (, ), [, ], {, and }. Return true if the brackets are balanced and false otherwise.
A string is balanced when:
- every opening bracket is closed by a bracket of the same type,
- brackets close in the reverse order they were opened, so pairs nest instead of crossing, and
- every closing bracket has an opening bracket before it to match.
The empty string is balanced.
Example 1
- Input
- s = "{[()]}()"
- Output
- true
Each bracket closes the most recent one still open.
Example 2
- Input
- s = "[{]}"
- Output
- false
The `]` arrives while `{` is the most recently opened bracket, so the pairs cross.
Example 3
- Input
- s = "(()"
- Output
- false
The first `(` is never closed.
Constraints
- 0 ≤ s.length ≤ 10⁴
- s contains only the characters ()[]{}.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Valid Parentheses in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Valid Parentheses
Pattern: Stack of open brackets
When a closing bracket shows up, the only bracket it is allowed to match is the most recently opened one that hasn't been closed yet. "Most recent first" is exactly what a stack gives you.
So push every opening bracket. On a closing bracket, the top of the stack must be its partner: if the stack is empty or the top is a different type, the string is invalid; otherwise pop and keep going. At the end, anything still on the stack was never closed.
With a single bracket type you could get away with a counter, but a counter can't tell [{]} from [{}]. The stack remembers which brackets are open, not just how many.
Approach 1: Repeatedly delete adjacent pairs
Keep removing every (), [], and {} substring until none are left. The string is valid if it ends up empty. Correct, but each pass rebuilds the string and a deeply nested input needs about n/2 passes.
Time O(n²) · Space O(n)
Approach 2: One pass with a stack
Map each closer to its opener: ) → (, ] → [, } → {. Then scan once:
- If the character is an opener, push it.
- If it's a closer, the stack must be non-empty and its top must equal the matching opener. Pop it; otherwise return false.
- After the loop, return whether the stack is empty.
An odd-length string can be rejected immediately, though the stack check catches it anyway.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Repeatedly delete adjacent pairs | O(n²) | O(n) |
| One pass with a stack | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Valid Parentheses solution in Python
def is_valid(s: str) -> bool:
opener = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in s:
if ch in opener:
if not stack or stack[-1] != opener[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stackValid Parentheses solution in JavaScript
function isValid(s) {
const opener = { ')': '(', ']': '[', '}': '{' };
const stack = [];
for (const ch of s) {
if (ch in opener) {
if (stack.length === 0 || stack[stack.length - 1] !== opener[ch]) return false;
stack.pop();
} else {
stack.push(ch);
}
}
return stack.length === 0;
}Common mistakes
- Popping from an empty stack when the string starts with a closer, which throws in Python and returns `undefined` in JavaScript.
- Forgetting the final empty-stack check, so `"(()"` passes.
- Using three separate counters, which accepts crossed pairs like `"[{]}"`.
- Returning true as soon as one matching pair is found instead of scanning the whole string.
What interviewers look for
Interviewers mostly want to hear why a stack: "a closer has to match the most recent unclosed opener, which is last-in, first-out." Say that before writing code.
Then list the three ways a string can fail (wrong type on top, nothing on the stack, leftovers at the end) and make sure your code handles each. Testing ")", "(", and "[{]}" out loud covers all three in under a minute.
Follow-up questions
What if the string also contains letters and other characters?
Skip any character that isn't a bracket. The stack logic is unchanged.
How would you find the length of the longest valid substring of a string of only ( and )?
Push indices instead of characters, starting with a sentinel -1. On `(` push its index; on `)` pop, and if the stack is now empty push the current index as the new base, otherwise the current valid run has length `i - stack.top`. Track the maximum. That is O(n).
What is the minimum number of insertions to make the string valid?
For a single bracket type, scan with a counter of open brackets: a `)` with no open bracket needs one insertion, and whatever is still open at the end needs one insertion each. Sum the two.
Companies that ask Valid Parentheses
Valid Parentheses is tagged by 180 companies in our interview dataset. The score shows how often it comes up at each company.
- Intuit100%
- Boeing100%
- Zenefits100%
- Freshworks100%
- Chewy100%
- Tripadvisor100%
- Odoo100%
- Bank Of America100%
- Weedmaps98%
- Walmart Labs95.2%
- Twitter93.7%
- Motorola93%
- Acxiom91%
- Ozon90%
- Zs Associates88.4%
- Zoho88.3%
- Intel88.1%
- Splunk87.7%
- Gopuff87%
- Affinipay87%
- Vk86.7%
- Millennium86.5%
- Mastercard86.1%
- Turing85.6%
and 156 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required