Valid Parentheses Solution for Amazon
Company: Amazon · Difficulty: Medium · Topics: String, Stack, Data Structure
Problem Statement
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.
Examples
Example 1:
Input: s = "()"
Output: true
Explanation: Simple valid parentheses.
Example 2:
Input: s = "()[]{}"
Output: true
Explanation: All brackets are properly closed.
Example 3:
Input: s = "(]"
Output: false
Explanation: Opening parenthesis is closed by wrong bracket.
Example 4:
Input: s = "([)]"
Output: false
Explanation: Brackets are not closed in correct order.
Example 5:
Input: s = "{[]}"
Output: true
Explanation: Nested brackets are properly closed.
Intuition
The key insight is that we need to match each closing bracket with its corresponding opening bracket. The last opening bracket should be closed first (LIFO - Last In, First Out), which suggests using a stack.
Approach
Approach 1: Stack (Optimal)
1. Use a stack to keep track of opening brackets
2. 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 it matches the top of the stack
- If match found, pop the stack; otherwise return false
3. At the end, check if stack is empty
Approach 2: Array as Stack
1. Use an array to simulate stack operations
2. Keep track of stack size manually
3. Same logic as stack approach but with array implementation
Approach 3: Character Counting (Limited)
1. Count opening and closing brackets
2. Only works for simple cases, fails for nested brackets
3. Not recommended for this problem
Dry Run
Let's trace through Example 4: s = "([)]"
Stack Approach:
- '(', push '(' → stack: ['(']
- '[', push '[' → stack: ['(', '[']
- ')', check top of stack '[' ≠ '(', return false
Array Approach:
- '(', push '(' → arr[0] = '(', size = 1
- '[', push '[' → arr[1] = '[', size = 2
- ')', check arr[1] = '[' ≠ '(', return false
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Stack (Optimal)
Time Complexity: O(n) - We traverse the string once
Space Complexity: O(n) - Stack can grow up to n elements
Solution 2: Array as Stack
Time Complexity: O(n) - Same as stack approach
Space Complexity: O(n) - Array can grow up to n elements
Solution 3: Character Counting
Time Complexity: O(n) - We traverse the string once
Space Complexity: O(1) - Only need counters
Note: This approach is limited and doesn't work for all cases.