Interview preparation
Valid Parentheses
1Problem statement
Given a string s containing only the characters ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type of bracket, and brackets must close in the correct order.
2Examples
3Constraints
- 1 ≤ s.length ≤ 10⁴
- s consists of brackets only.
4Approaches
Approach 1
Brute Force
Repeatedly delete adjacent pairs '()', '[]', '{}' until nothing changes; valid if the string becomes empty.
Approach 2
Better: Counters
Counting open/close per type catches unbalanced counts but fails on order like '([)]' — useful to see why order needs a stack.
Approach 3
Optimal: Stack
Push opening brackets. For a closing bracket the top of the stack must be its matching opener; pop it. At the end the stack must be empty.
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
function isValid(s) {
const pairs = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const ch of s) {
if (ch === "(" || ch === "[" || ch === "{") {
stack.push(ch);
} else if (stack.length === 0 || stack.pop() !== pairs[ch]) {
return false;
}
}
return stack.length === 0;
}
for (const s of ["()[]{}", "(]", "([)]", "{[]}"]) {
console.log(s, isValid(s));
}
6Complexity
Time
O(n)
Space
O(n)
7Visual walkthrough
- 1.s = "{[]}": push "{" → stack ["{"]
- 2.push "[" → stack ["{", "["]
- 3."]" matches top "[" → pop → stack ["{"]
- 4."}" matches top "{" → pop → stack [] → empty, so valid
Related visualization (Stack Push and Pop) — shows the core data-structure operations this solution relies on:
Size 0 / 3 · LIFO — the last value pushed is the first one popped
A stack is Last-In-First-Out (LIFO): push adds to the top, pop removes from the top. A fixed capacity shows overflow (push when full) and underflow (pop when empty).