FAANGPrep Sprint
Valid Parentheses
Determine if the input string has valid matching brackets.
Problem Understanding
The string s is made only of the bracket characters (, ), {, }, [ and ]. Decide whether it is balanced.
It is balanced when:
- Every opening bracket is closed by a bracket of the same kind.
- Brackets close in reverse order of opening, so the most recently opened one closes first.
Example:
- Input:
s = "()[]{}"-> Output:true - Input:
s = "(]"-> Output:false - Input:
s = "([)]"-> Output:false
Algorithm Strategy
We use a Stack data structure.
- Iterate through the string char by char.
- If we see an open bracket (
(,{,[), push it onto the stack. - If we see a close bracket (
),},]), check the top of the stack:- If stack is empty, it's invalid (no matching open).
- If stack top is the matching open bracket, pop the stack.
- Otherwise, it's a mismatch -> invalid.
- At the end, stack must be empty (all opened brackets were closed).
Interactive Visualization
"({[]})"
READ
string
i
(
0
{
1
[
2
]
3
}
4
)
5
stack
empty
Open
0
Needs
—
Answer
—
Read '(' at 0
Next
'(' opens a group: push it. It must be closed before anything below it
String
Legend & Complexity
The character being read
Already matched
The top opener a closer is checked against
A closer with no matching opener on top
Time
O(n)
Space
O(n)
Watch how the stack grows with open brackets and shrinks with matching closed ones.
Dry Run
Input: ({[]})
| Step | Char | Action | Stack |
|---|---|---|---|
| 1 | ( |
Push | ( |
| 2 | { |
Push | ( { |
| 3 | [ |
Push | ( { [ |
| 4 | ] |
Match [? Yes. Pop. |
( { |
| 5 | } |
Match {? Yes. Pop. |
( |
| 6 | ) |
Match (? Yes. Pop. |
Empty |
| End | - | Stack Empty? Yes. | Valid |
Edge Cases & Common Mistakes
- Empty String: Usually valid (unless constraints say otherwise).
- Odd Length: Automatically invalid.
- Start with Close:
]...invalid immediately. - Leftovers:
(()stack not empty at end.
Solution
Stack implementation.
Valid Parentheses Code
1var isValid = function(s) {2 const stack = [];3 const pairs = { ')': '(', ']': '[', '}': '{' };4 for (const ch of s) {5 if (!(ch in pairs)) {6 stack.push(ch);7 } else if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) {8 return false;9 } else {10 stack.pop();11 }12 }13 return stack.length === 0;14};