Coding Interview PatternsValid Parentheses
EasyStacks
Valid Parentheses
Explanation & Solution
Description
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Input: s = "()"
Output: true
Constraints
1 <= s.length <= 10^4sconsists of parentheses only'()[]{}'
Approach
Stacks pattern
1. Initialize a Stack
- Create an empty stack to track opening brackets
- Create a mapping from closing brackets to their corresponding opening brackets
2. Iterate Through Each Character
- For each character in the string:
- If it's an opening bracket (
(,{,[), push it onto the stack - If it's a closing bracket (
),},]): - Check if the stack is empty (no matching opener) → invalid
- Check if the top of stack matches the expected opener → if not, invalid
- If it matches, pop the top of the stack
3. Final Check
- After processing all characters, the string is valid only if the stack is empty
- A non-empty stack means there are unmatched opening brackets
Key Insight
- The stack naturally enforces the nesting order — the most recently opened bracket must be closed first (LIFO)
- This is the canonical introductory stack problem with O(n) time and O(n) space
Visualization
Input:
[(, )]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
3 steps