#20
Valid Parentheses
Easy Stack matching
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a string of ()[]{} brackets is balanced: every opener is closed by the same type, in the right order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: does every bracket close in the right order?
Why this works: the most recent unclosed bracket must close first — that's a stack.
Example: "([]{})"
push ) ] → pop ] ✓ → push } → pop } ✓ → pop ) ✓stack empty → valid
✦Hints open one at a time
The most recent unclosed opener must be closed first — that's a stack.
Push the expected closer when you see an opener; when you see a closer, pop and compare.
↗Approach
Use an ArrayDeque as a stack. For an opener push its matching closer. For a closer, the stack must be non-empty and its top must equal it. At the end the stack must be empty.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '[') stack.push(']');
else if (c == '{') stack.push('}');
else if (stack.isEmpty() || stack.pop() != c) return false; // wrong or missing opener
}
return stack.isEmpty();
}
}!Common mistake
Forgetting to check that the stack is empty at the end ("((" is not valid).
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon