How do you solve Valid Parentheses on LeetCode?

Valid Parentheses (LeetCode #20) can be solved using Brute Force or Optimal Solution (Stack). The optimal approach is Optimal Solution (Stack) with O(n) time complexity and O(n) space complexity. Key insight: The use of a stack is crucial for problems involving matching pairs, as it allows us to track the most recent unmatched opening bracket.

What is the brute force solution for Valid Parentheses?

The brute force approach for Valid Parentheses is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking all possible combinations of parentheses to see if they can be valid. This method is straightforward but inefficient as it doesn't leverage any data structures to manage the order of brackets. The optimal Optimal Solution (Stack) approach improves this to O(n).

What algorithm or data structure is used to solve Valid Parentheses?

Valid Parentheses uses the following concepts: String, Stack. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Valid Parentheses?

When you first see this problem, mention that you will use a stack to track opening brackets and ensure they are closed in the correct order. Communicate your approach clearly, explaining how the stack will help manage unmatched brackets. Mention edge cases such as an empty string (which should return true) or strings with only closing brackets (which should return false).

What are common mistakes when solving Valid Parentheses?

Forgetting to check if the stack is empty before popping, which can lead to runtime errors. Not correctly mapping closing brackets to their corresponding opening brackets, leading to incorrect results.

#20

Valid Parentheses

Easy

StringStackHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Stack)★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a stack allows us to efficiently track opening brackets and ensure they are closed in the correct order. This approach is optimal because it processes each character once, leveraging the stack to manage the state of unmatched opening brackets.

⚙️

Algorithm

5 steps

1Step 1: Initialize an empty stack.
2Step 2: Iterate through each character in the string.
3Step 3: If the character is an opening bracket ('(', '{', or '['), push it onto the stack.
4Step 4: If the character is a closing bracket (')', '}', or ']'), check if the stack is empty. If it is, return false. If not, pop the top of the stack and check if it matches the corresponding opening bracket. If it doesn't match, return false.
5Step 5: After processing all characters, if the stack is empty, return true; otherwise, return false.

solution.py20 lines

1# Full working Python code with comments
2
3def isValid(s: str) -> bool:
4    stack = []
5    mapping = {')': '(', '}': '{', ']': '['}
6    for char in s:
7        if char in mapping.values():  # If it's an opening bracket
8            stack.append(char)
9        elif char in mapping.keys():  # If it's a closing bracket
10            if not stack or stack[-1] != mapping[char]:
11                return False
12            stack.pop()  # Pop the last opening bracket
13    return not stack  # Return True if stack is empty
14
15# Example usage
16print(isValid('()'))  # Output: True
17print(isValid('()[]{}'))  # Output: True
18print(isValid('(]'))  # Output: False
19print(isValid('([])'))  # Output: True
20print(isValid('([)]'))  # Output: False

ℹ

Complexity note: The time complexity is O(n) because we traverse the string once, and the space complexity is O(n) because in the worst case, we may store all opening brackets in the stack.

1The use of a stack is crucial for problems involving matching pairs, as it allows us to track the most recent unmatched opening bracket.
2Recognizing that each closing bracket must correspond to the last unmatched opening bracket is key to understanding the order requirement.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.