#20 Valid Parentheses
frequently reported atIntuitWalmartBloombergLinkedInNVIDIAAmazon
the problem
In plain words
A string contains only the characters ( ) [ ] { }. It is valid if every opening bracket is closed by the same type of bracket, in the correct order, and every closer has an opener. Return true if it is valid.
in s = "()[]{}"
out true
in s = "(]"
out false
'(' is closed by a different type.
in s = "([)]"
out false
The ']' arrives while '(' is the most recent opener.
in s = "{[]}"
out true
- 1 ≤ s.length ≤ 10⁴
- s consists only of '()[]{}'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternStack for matching & nesting
where this runsParsers catch an unmatched bracket the same way: each open bracket waits on a stack (or on the parser's own call stack) until its partner arrives.
A closer must match the most recent opener that is still open. "Most recent first" is exactly what a stack gives you.
solutions
From brute force to optimal
A valid string always contains an adjacent pair like (). Keep deleting such pairs; valid strings shrink to empty.
- Replace every "()", "[]" and "{}" with nothing.
- Repeat while the string keeps changing.
- Valid if the string ends up empty.
Each pass is O(n) and removes at least one pair, so up to n/2 passes (think "((((...))))").
Each pass builds a new String.
class Solution { public boolean isValid(String s) { String prev; do { // delete innermost pairs until nothing changes prev = s; s = s.replace("()", "").replace("[]", "").replace("{}", ""); } while (!s.equals(prev)); return s.isEmpty(); }}Push every opener. On a closer, the top of the stack must be its partner.
- For each char: opener → push it.
- Closer → if the stack is empty, invalid. Otherwise pop and check the pair matches.
- At the end, valid only if the stack is empty (no opener left unclosed).
One pass; each character is pushed and popped at most once.
All openers, e.g. "((((((", sit on the stack.
class Solution { public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { if (stack.isEmpty()) return false; char open = stack.pop(); if (!matches(open, c)) return false; } } return stack.isEmpty(); } private boolean matches(char open, char close) { return (open == '(' && close == ')') || (open == '[' && close == ']') || (open == '{' && close == '}'); }}Dry run
On an opener, push the closer you'll need. On a closer, the popped value must equal it — no lookup table.
- Odd length → false immediately.
- '(' → push ')', '[' → push ']', '{' → push '}'.
- Closer → stack empty or pop() ≠ c → false.
- Return stack.isEmpty().
One pass.
Up to n expected closers when every character is an opener, e.g. "((((".
class Solution { public boolean isValid(String s) { if (s.length() % 2 == 1) return false; // odd length can never balance Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); // remember what must close it else if (c == '[') stack.push(']'); else if (c == '{') stack.push('}'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); }}in the room
How to say it in the interview
talk track
- Clarify: only bracket characters? Is the empty string valid? (Yes on LeetCode, though length ≥ 1.)
- Say: "A closer must match the most recent unmatched opener, so I'll keep openers on a stack."
- Call out both failure modes: a closer with an empty stack, and openers left over at the end.
- Mention the odd-length early exit as a cheap optimisation.
traps
- Returning true at the end without checking that the stack is empty — "((" would pass.
- Calling pop() on an empty stack for input ")" —
ArrayDequethrows.
what they ask next
Follow-ups
Only one bracket type, e.g. just '(' and ')'?
You don't need a stack — a depth counter is enough: +1 for '(', −1 for ')', fail if it goes negative, succeed if it ends at 0. O(1) space.
Minimum Remove to Make Valid Parentheses (LC 1249)?
Push indices of '(' ; mark unmatched ')' for removal while scanning; whatever indices remain on the stack are unmatched '(' to remove too.
before you submit
Edge cases to test
- A lone closer like ")": the stack is empty when it arrives — check before you pop.
- Openers left over: "((" has even length and no mismatch, yet it is invalid.
- Interleaved types: "([)]" has the right counts but the wrong order.
practise next
Similar problems
- #32Longest Valid ParenthesesHardin Stacks
- #394Decode StringMediumin Stacks
- #22Generate ParenthesesMediumin Backtracking