Valid Parentheses
Check if a string of brackets is properly balanced
Given a string s containing only characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: (1) open brackets are closed by the same type, (2) brackets are closed in the correct order, and (3) every close bracket has a corresponding open bracket.
R — READ
READ
What makes a string of brackets 'valid'?
Three rules: (1) every type matches, (2) correct order, (3) every close has an open.
Do you understand all three conditions? Do you ask: should I handle empty strings? Spaces?
Assuming 'valid' just means 'all closed' without checking type or order.
Input: s = "()"
Output: true
Input: s = "([{}])"
Output: true
Input: s = "([)]"
Output: false (wrong order)
O — OBSERVE
OBSERVE
How do brackets relate to each other?
Open brackets should be matched by closes in reverse order (LIFO). A stack is perfect: push opens, pop and check when you see closes.
Can you recognize the LIFO pattern and connect it to a stack?
Trying to solve with a single counter or string substitution.
Example: "({[]})"
Stack progression:
• '(' → push, stack: ['(']
• '{' → push, stack: ['(', '{']
• '[' → push, stack: ['(', '{', '[']
• ']' → top is '[', matches, pop. stack: ['(', '{']
• '}' → top is '{', matches, pop. stack: ['(']
• ')' → top is '(', matches, pop. stack: []
Empty stack at end = valid
P — PSEUDOCODE
PSEUDOCODE
How do I use a stack to solve this?
For each character: push opens, pop and verify closes. At the end, stack must be empty.
Sound algorithm before coding.
Pseudocode that skips the type-matching logic.
1. Create an empty stack
2. Create a mapping of close → open brackets
3. For each character in the string:
a. If it's an open bracket, push to stack
b. If it's a close bracket:
i. If stack is empty, return false (no matching open)
ii. Pop the top. If it doesn't match, return false
4. If loop ends and stack is empty, return true
5. If stack is not empty, return false
I — IMPLEMENT
IMPLEMENT
How do I turn this into code?
Use a list as a stack in Python. Create a dict for type matching.
Clean, readable code. Correct type matching.
Off-by-one errors or forgetting to check if stack is empty.
def isValid(s):
"""
Check if a string of brackets is valid.
Args:
s: String containing only brackets
Returns:
True if valid, False otherwise
"""
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs: # It's a closing bracket
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
else: # It's an opening bracket
stack.append(char)
return len(stack) == 0
T — TEST
TEST
Does my code work on all cases?
Test: valid strings, invalid types, invalid order, empty, unmatched.
Thoroughness and edge case handling.
Only testing valid cases.
Test 1: "()" → True ✓
Test 2: "([{}])" → True ✓
Test 3: "([)]" → False (wrong order) ✓
Test 4: "" → True (empty is valid) ✓
Test 5: "(" → False (unmatched open) ✓
Test 6: ")" → False (unmatched close) ✓
Test 7: "([)]" → False (interleaved) ✓
A — ANALYZE
ANALYZE
What's the complexity?
One pass through the string. Each element pushed and popped at most once.
Correct Big O reasoning.
Claiming O(n²) or not accounting for amortized cost.
Why: We iterate through the string once (O(n)). Each character is pushed or popped from the stack once, so operations are O(n) total. The stack can hold up to n characters in the worst case (all opens).
Note: This is optimal because we must at least read every character once.