Introduction to Valid Parentheses
The Valid Parentheses problem is one of the most iconic algorithmic challenges you'll encounter in coding interviews and competitive programming. At its core, it asks a deceptively simple question: given a string containing only the characters (, ), {, }, [, and ], determine if the input string is valid. A string is considered valid when every opening bracket has a corresponding closing bracket of the same type, and they are closed in the correct order.
This problem appears frequently on platforms like LeetCode (Problem #20), and it's a favorite among interviewers because it elegantly tests your understanding of the stack data structure. In this tutorial, we'll walk through the problem from first principles, build a working Python solution, and explore best practices and edge cases.
What Is the Valid Parentheses Problem?
Before writing any code, let's clearly define what "valid" means. A parentheses string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Here are some examples to clarify:
"()"— valid"()[]{}"— valid"(]"— invalid (mismatched types)"([)]"— invalid (incorrect order)"{[]}"— valid (properly nested)""— valid (empty string)
The key insight is that brackets must nest properly, much like physical containers. If you open a box, then open another inside it, you must close the inner box before closing the outer one. This "last-in, first-out" behavior is exactly what a stack is designed to model.
Why This Problem Matters
You might wonder why such a seemingly simple problem deserves so much attention. The answer lies in both its practical applications and its educational value.
Real-World Applications
Bracket validation isn't just an academic exercise. It's fundamental to:
- Compilers and interpreters: Every programming language parser must validate that braces, brackets, and parentheses are balanced before parsing code into an abstract syntax tree.
- Code editors: IDEs like VS Code and PyCharm perform real-time bracket matching to highlight syntax errors as you type.
- JSON and XML parsing: These data formats rely on properly nested delimiters, and parsers must validate structure before processing.
- Mathematical expression evaluation: Calculators and symbolic math engines need to verify that parentheses in expressions like
(3 + (4 * 2))are balanced. - HTML/XML tag matching: Ensuring that opening tags have corresponding closing tags in the right order.
Educational Value
From a learning perspective, this problem is a perfect introduction to the stack data structure. It teaches you how to:
- Recognize when a problem has LIFO (Last-In, First-Out) characteristics.
- Use a hash map for clean, maintainable lookups.
- Handle edge cases like empty strings and single characters.
- Reason about time and space complexity.
Understanding the Stack Approach
The stack is the natural data structure for this problem. A stack is a linear collection where you add and remove elements only from one end (the top). Think of it like a stack of plates: you add a plate to the top, and you remove the topmost plate first.
Here's the algorithm in plain English:
- Create an empty stack.
- Create a mapping of closing brackets to their corresponding opening brackets.
- Iterate through each character in the string.
- If the character is an opening bracket, push it onto the stack.
- If the character is a closing bracket, check the top of the stack. If the stack is empty or the top doesn't match the corresponding opening bracket, the string is invalid.
- If it matches, pop the opening bracket from the stack.
- After processing all characters, the stack should be empty. If it is, the string is valid; otherwise, it's invalid.
Why map closing brackets to opening brackets? Because when we encounter a closing bracket, we need to look up what opening bracket it expects. Storing this in a dictionary makes the code clean and extensible.
Step-by-Step Python Implementation
Now let's translate the algorithm into Python code. We'll build it up incrementally.
Step 1: The Basic Structure
First, we define the function and set up our stack and mapping:
def is_valid(s: str) -> bool:
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
# We'll fill this in next
pass
return len(stack) == 0
The bracket_map dictionary uses closing brackets as keys and their corresponding opening brackets as values. This design choice makes lookups during iteration straightforward.
Step 2: Handling Opening Brackets
When we encounter an opening bracket, we push it onto the stack:
def is_valid(s: str) -> bool:
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map.values():
stack.append(char)
return len(stack) == 0
Checking char in bracket_map.values() tells us if the character is an opening bracket. However, this is slightly inefficient because values() creates a view that must be scanned. A cleaner approach is to check if the character is not a closing bracket key.
Step 3: Handling Closing Brackets
When we encounter a closing bracket, we need to verify it matches the most recent opening bracket:
def is_valid(s: str) -> bool:
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
# It's a closing bracket
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
else:
# It's an opening bracket
stack.append(char)
return len(stack) == 0
Let's break down the closing bracket logic:
if not stack— If the stack is empty, there's no opening bracket to match, so the string is invalid.stack[-1] != bracket_map[char]— If the top of the stack doesn't match the expected opening bracket for this closing bracket, the string is invalid.stack.pop()— If both checks pass, remove the matched opening bracket.
Step 4: The Complete Solution
Here's the complete, clean solution with type hints and a docstring:
def is_valid(s: str) -> bool:
"""
Determine if the input string containing parentheses is valid.
A string is valid if:
1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
Args:
s: A string containing only '(', ')', '{', '}', '[', ']'
Returns:
True if the string is valid, False otherwise
"""
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
Note that we changed len(stack) == 0 to not stack. This is more Pythonic and slightly more efficient, as it avoids a function call.
Testing the Solution
A robust solution needs thorough testing. Let's write test cases covering various scenarios:
def test_is_valid():
# Basic valid cases
assert is_valid("()") == True
assert is_valid("()[]{}") == True
assert is_valid("{[]}") == True
assert is_valid("([{}])") == True
# Basic invalid cases
assert is_valid("(]") == False
assert is_valid("([)]") == False
assert is_valid("(") == False
assert is_valid(")") == False
# Edge cases
assert is_valid("") == True # Empty string is valid
assert is_valid("(((((((((())))))))))") == True # Deeply nested
assert is_valid("(((((((((()))))))))))") == False # Extra closing
assert is_valid("(((") == False # Only opening brackets
assert is_valid(")))") == False # Only closing brackets
# Mixed valid sequences
assert is_valid("()()()()") == True
assert is_valid("{}{}()[]") == True
print("All tests passed!")
test_is_valid()
Run this, and if you see "All tests passed!", your implementation is correct. These test cases cover the happy path, mismatched types, incorrect ordering, unmatched brackets, empty strings, and deeply nested structures.
Tracing Through an Example
To solidify your understanding, let's trace through the input "{[]}" step by step:
Input: "{[]}"
Stack: []
bracket_map = {')': '(', '}': '{', ']': '['}
Iteration 1: char = '{'
'{' not in bracket_map (it's an opening bracket)
stack.append('{')
Stack: ['{']
Iteration 2: char = '['
'[' not in bracket_map (it's an opening bracket)
stack.append('[')
Stack: ['{', '[']
Iteration 3: char = ']'
']' in bracket_map (it's a closing bracket)
stack is not empty, stack[-1] = '[' == bracket_map[']'] = '[' ✓
stack.pop()
Stack: ['{']
Iteration 4: char = '}'
'}' in bracket_map (it's a closing bracket)
stack is not empty, stack[-1] = '{' == bracket_map['}'] = '{' ✓
stack.pop()
Stack: []
End of string: stack is empty → return True
Now let's trace an invalid input, "([)]":
Input: "([)]"
Stack: []
Iteration 1: char = '(' → opening, push → Stack: ['(']
Iteration 2: char = '[' → opening, push → Stack: ['(', '[']
Iteration 3: char = ')' → closing, stack[-1] = '[' != bracket_map[')'] = '(' → return False
The algorithm catches the mismatch immediately when ) tries to close [ instead of (.
Complexity Analysis
Understanding the efficiency of your solution is crucial, especially in interviews.
Time Complexity
The time complexity is O(n), where n is the length of the string. We iterate through each character exactly once, and each stack operation (append and pop) is O(1). Dictionary lookups in Python are also O(1) on average.
Space Complexity
The space complexity is O(n) in the worst case. If the string consists entirely of opening brackets, like "(((((", we push every character onto the stack without ever popping. In the best case (a valid string with balanced brackets), the stack never grows larger than n/2, but we still express this as O(n) since it scales linearly with input size.
Alternative Approaches
While the stack approach is the most common and recommended solution, it's worth knowing alternatives.
Without a Stack: String Replacement
A clever but less efficient approach repeatedly removes valid pairs from the string:
def is_valid_no_stack(s: str) -> bool:
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()', '').replace('[]', '').replace('{}', '')
return s == ''
This works because valid pairs are removed iteratively until none remain. If the string is valid, it becomes empty. However, this approach is O(n²) in the worst case because each replace call scans the entire string, and we may do n/2 passes. It's elegant but not suitable for large inputs.
Using a Counter (Single Bracket Type)
If the problem only involved one type of bracket, like ( and ), you could use a simple counter instead of a stack:
def is_valid_single_type(s: str) -> bool:
count = 0
for char in s:
if char == '(':
count += 1
else:
if count == 0:
return False
count -= 1
return count == 0
This uses O(1) space, but it only works for a single bracket type. With multiple types, you need the stack to remember which opening bracket was used.
Best Practices
Here are some best practices to keep in mind when implementing and using this solution:
1. Use a Dictionary for Bracket Mapping
Always use a dictionary to map brackets rather than writing long if-elif chains. This makes the code cleaner, more maintainable, and easier to extend if you need to support additional bracket types:
# Easy to extend with new bracket types
bracket_map = {
')': '(',
'}': '{',
']': '[',
'>': '<', # Adding angle brackets
}
2. Early Returns for Efficiency
Return False as soon as you detect an invalid condition. Don't process the entire string if you can determine invalidity early. This is especially beneficial for long strings with errors near the beginning.
3. Validate Input
In production code, consider validating that the input contains only valid characters:
def is_valid_robust(s: str) -> bool:
valid_chars = set('()[]{}')
if not all(c in valid_chars for c in s):
raise ValueError("String contains invalid characters")
stack = []
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
4. Use Pythonic Idioms
Prefer not stack over len(stack) == 0. Use stack[-1] for peeking instead of stack[len(stack) - 1]. These idioms make your code more readable to experienced Python developers.
5. Write Comprehensive Tests
Always test edge cases: empty strings, single characters, deeply nested structures, and strings with only opening or only closing brackets. A solution that passes basic tests can still fail on edge cases.
6. Consider Using collections.deque for Large Inputs
Python lists work fine as stacks, but if you're dealing with extremely large inputs, collections.deque offers O(1) append and pop operations from both ends, with slightly better performance characteristics:
from collections import deque
def is_valid_deque(s: str) -> bool:
stack = deque()
bracket_map = {')': '(', '}': '{', ']': '['}
for char in s:
if char in bracket_map:
if not stack or stack[-1] != bracket_map[char]:
return False
stack.pop()
else:
stack.append(char)
return not stack
In practice, for most interview and real-world scenarios, a plain list is perfectly adequate. The difference only matters at scale.
Common Mistakes to Avoid
When solving this problem, developers often make these errors:
- Forgetting to check if the stack is empty before peeking: Accessing
stack[-1]on an empty list raises anIndexError. Always checkif not stackfirst. - Mapping opening to closing instead of closing to opening: If you map
'(': ')', you'll need to search the stack for a match, which defeats the purpose of the stack approach. - Not checking the stack at the end: A string like
"((("will pass all character checks but leave brackets on the stack. The finalreturn not stackis essential. - Using
==instead of!=in the mismatch check: This logical error causes the function to returnFalsefor valid matches.
Extending the Problem
Once you've mastered the basic Valid Parentheses problem, try these related challenges to deepen your understanding:
- Generate Parentheses: Generate all combinations of well-formed parentheses for a given
npairs. - Longest Valid Parentheses: Find the length of the longest valid (well-formed) parentheses substring.
- Remove Invalid Parentheses: Remove the minimum number of invalid parentheses to make the string valid.
- Valid Parenthesis String: Handle strings with
*characters that can act as either(or)or empty.
Each of these builds on the stack intuition you've developed here while introducing new algorithmic concepts like backtracking, dynamic programming, and greedy approaches.
Conclusion
The Valid Parentheses problem is a foundational algorithmic challenge that every developer should master. It elegantly demonstrates the power of the stack data structure for solving problems with nested, last-in-first-out structure. By using a dictionary to map bracket pairs and a stack to track opening brackets, you can solve the problem in O(n) time and O(n) space with clean, readable code. Remember to handle edge cases like empty strings and unmatched brackets, write comprehensive tests, and use Pythonic idioms for maintainability. Whether you're preparing for a coding interview or building a parser for a real-world application, the principles you've learned here will serve you well across a wide range of programming challenges.