Valid Parentheses
Understand the problem
Given a string s containing only the characters ()[]{}, return true if the brackets are valid: every opening bracket has a closing bracket of the same type, and they close in the correct order.
s = "()[]{}" → true
s = "([])" → true // correctly nested
s = "(]" → false // wrong type
s = "([)]" → false // wrong nesting orderThe main idea: the most recent opening bracket must be closed first. "Most recent, handled first" is exactly the LIFO property of a stack.
Show the basic approach (slower)
O(n²) time, O(n) spacefunction isValidNaive(s: string): boolean {
let prev = ''
// Keep removing adjacent pairs "()", "[]", "{}" until none are left to remove
while (prev !== s) {
prev = s
s = s.replace('()', '').replace('[]', '').replace('{}', '')
}
return s.length === 0
}Each replace rescans almost the whole string, and you have to repeat until the string stops changing.
A string like "(((...)))" makes the number of rounds proportional to its length → O(n²).
Optimal solution
O(n) time, O(n) spacefunction isValid(s: string): boolean {
const stack: string[] = []
const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
for (const ch of s) {
if (ch === '(' || ch === '[' || ch === '{') {
stack.push(ch)
} else {
// closing char: stack top must be the matching opener
// empty stack → return false right away (closer with no opener before it)
if (!stack.length || stack.pop() !== pairs[ch]) return false
}
}
return stack.length === 0
}The optimal approach: on an opening bracket, push it onto the stack; on a closing bracket, pop the top and check that it matches — the top is the most recent opening bracket not yet closed.
- A wrong type, or an empty stack on pop → invalid.
- At the end the stack must be empty (no leftover opening brackets).
Step-by-step trace
1function isValid(s: string): boolean {2 const stack: string[] = []3 const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }4 5 for (const ch of s) {6 if (ch === '(' || ch === '[' || ch === '{') {7 stack.push(ch)8 } else {9 // closing char: stack top must be the matching opener10 // empty stack → return false right away (closer with no opener before it)11 if (!stack.length || stack.pop() !== pairs[ch]) return false12 }13 }14 15 return stack.length === 016}Edge cases to remember
Empty string "" → the stack is empty → true.
A lone opening bracket "(" → the stack still has an element at the end → false.
Starts with a closing bracket ")" → pop() on an empty stack returns undefined ≠ pairs → false.
An odd number of brackets → they can't all match → false.