Jump to section
Valid Parentheses asks whether a string of brackets is balanced: every opening bracket is closed by the same type, in the right order. The standard solution pushes opening brackets onto a stack and, for each closing bracket, checks that it matches the top of the stack. It runs in O(n) time and O(n) space.
The Valid Parentheses Problem
You are given a string made only of the characters ( ) [ ] { }. Decide whether it is valid. A string is valid when every opening bracket has a closing bracket of the same type, brackets close in the reverse order they opened, and no closing bracket appears without a matching opener. An empty string counts as valid.
Example 1
Input: "{[()]}"
Output: true
Why: each bracket closes the most recent one that is still open.
Example 2
Input: "([)]"
Output: false
Why: the counts match, but ] arrives while ( is the most recent open bracket, so the nesting is wrong.
Assumptions to confirm
- Only bracket characters, or other text too? (If other characters appear, skip them.)
- Is an empty string valid? (Usually yes.)
- How long can the string be? (It does not change the approach, but it tells you whether recursion would be risky.)
Start With the Brute Force
A naive approach repeatedly deletes adjacent matching pairs such as "()", "[]" and "{}" until nothing changes, then checks whether the string is empty. It works, but each pass is O(n) and you may need O(n) passes, so it is O(n²) time.
Counting brackets is the other tempting shortcut, and it is wrong: "([)]" has equal counts of every type and is still invalid. Mentioning why counting fails is a quick way to show you understand that order matters, which is exactly what a stack captures.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
The Optimal Approach: A Stack
Map each closing bracket to its opener
A small dictionary such as ) to ( lets you check a match in one lookup.
Push every opening bracket
The top of the stack is always the bracket that must close next.
On a closing bracket, check the top
If the stack is empty or the top is not the matching opener, the string is invalid. Otherwise pop it.
Finish with an empty stack
Anything left on the stack is an opener that was never closed, so the string is only valid if the stack is empty.
Valid Parentheses in Python and TypeScript
Both versions use a plain array as the stack. In TypeScript, popping an empty array returns undefined, which never equals an opener, so one comparison covers both the empty and the mismatch case.
Python
def is_valid(s: str) -> bool:
pairs = {")": "(", "]": "[", "}": "{"}
stack: list[str] = []
for ch in s:
if ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else:
stack.append(ch)
return not stackTypeScript
function isValid(s: string): boolean {
const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
const stack: string[] = [];
for (const ch of s) {
if (ch in pairs) {
if (stack.pop() !== pairs[ch]) return false;
} else {
stack.push(ch);
}
}
return stack.length === 0;
}Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Time and Space Complexity
| Approach | Time | Space | When to use it |
|---|---|---|---|
| Repeatedly delete "()" pairs | O(n²) | O(n) for new strings | Only as a stepping stone |
| Count each bracket type | O(n) | O(1) | Never: it accepts "([)]" |
| Stack of open brackets | O(n) | O(n) | The expected interview answer |
How to Talk Through It in an Interview
- Clarify: "Only bracket characters? Is the empty string valid?"
- Brute force: "I could keep deleting matching adjacent pairs until the string stops changing, but that is quadratic. Counting is not enough, because order matters."
- Optimise: "The bracket that must close next is always the most recently opened one, which is last in, first out, so a stack fits."
- Code: point out the two ways to fail: a closer with nothing to match, and openers left over at the end.
- Test: run "{[()]}", "([)]", ")" and "((" through it, plus the empty string.
Ready to put this into practice?
Practice this with MockIF →Still applying for jobs? Let Auto Apply do it
Edge Cases and Common Follow-Ups
A string that starts with a closer
Such as ")(": the stack is empty when ) arrives, so return false immediately.
Odd length
A string with an odd number of brackets can never be valid, so you can return false up front as a small optimisation.
Minimum additions to make it valid
Track unmatched openers and unmatched closers as you scan; their sum is the answer for a single bracket type.
Longest valid substring
Push indexes instead of characters and measure the distance to the last unmatched position.
Generate all valid combinations
Backtracking: add an opener while you have some left, and a closer only when it would not exceed the openers used.
Practise Valid Parentheses in a Mock Coding Round
Reading a solution is not the same as producing one with someone listening. The gap shows up as long silences, a jump straight to code without a brute force, or a bug you only spot after the interviewer asks you to test. The fix is to rehearse problems like Valid Parentheses out loud, under time pressure, while explaining each decision.
MockIF runs mock coding interviews with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, adds follow-up questions the way a real interviewer would, and then scores your answer and gives specific feedback. Each session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing).
Frequently Asked Questions
Why is a stack used for valid parentheses?
What is the time complexity of the stack solution?
Can you solve valid parentheses without a stack?
Is an empty string valid?
What are the most common mistakes?
Stop Preparing in Your Head. Start Practicing Out Loud.
Drop your resume, add a job description, and get a mock interview like the real thing.
Start Free Mock Interview →Still applying for jobs? Let Auto Apply do it for you.