How to Solve: Valid Parentheses – Complete Guide for FAANG Interviews

How to Solve: Valid Parentheses – Complete Guide for FAANG Interviews

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—nail it and you show clear problem-solving maturity, stack mastery, and attention to edge cases."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Valid Parentheses, ensure you understand: 1. Stack Data Structure – LIFO (Last-In-First-Out) operations (push, pop, peek). 2. Hash Maps (Dictionaries) – O(1) lookups for key-value pairs. 3. String Iteration & Indexing – Traversing characters in a string efficiently.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Run this exact checklist for every Valid Parentheses problem:

1. Check Edge Cases First
2. If string length is odd → Invalid (immediate return).

3. If string is empty → Valid (return True).

4. Initialize a Stack

5. Use a list (Python) or Deque (Java) for O(1) pop() and append().

6. Define a Hash Map for Pairs

7. Map closing brackets to their opening counterparts:
   python
pairs = {')': '(', '}': '{', ']': '['}

8. Iterate Through Each Character

9. For each char in the string:

   • If char is a closing bracket (char in pairs):
   • If stack is empty → Invalid (no matching opening).
   • If stack.pop() != pairs[char] → Invalid (mismatch).
   • Else (opening bracket) → stack.append(char).

10. Final Stack Check

11. If stack is empty → Valid (all brackets matched).

12. Else → Invalid (unmatched opening brackets).

13. Return Result

14. True if valid, False otherwise.

? WORKED EXAMPLES

Example 1 – Basic: Valid Parentheses (LeetCode 20)

Problem: Given a string s containing '()[]{}', determine if it is valid.

Walkthrough: 1. Edge Cases:
- s = "()" → Length 2 (even) → Proceed.
- s = "(" → Length 1 (odd) → Invalid. 2. Initialize:
- stack = []
- pairs = {')': '(', '}': '{', ']': '['} 3. Iterate:
- s = "()[]{}"
- '(' → stack = ['(']
- ')' → stack.pop() == '(' → Match → stack = []
- '[' → stack = ['[']
- ']' → stack.pop() == '[' → Match → stack = []
- '{' → stack = ['{']
- '}' → stack.pop() == '{' → Match → stack = [] 4. Final Check:
- stack is empty → Valid.

Code (Python):

def isValid(s: str) -> bool:

    if len(s) % 2 != 0:

        return False

    stack = []

    pairs = {')': '(', '}': '{', ']': '['}

    for char in s:

        if char in pairs:

            if not stack or stack.pop() != pairs[char]:

                return False

        else:

            stack.append(char)

    return not stack

Complexity: - Time: O(n) (single pass through the string). - Space: O(n) (worst-case stack stores all opening brackets).

Why This Works: - The stack ensures LIFO order (last opened must close first). - The hash map decouples the logic for different bracket types.

Example 2 – Medium: Valid Parentheses with Wildcards (Follow-up)

Problem: Given a string s with '()[]{}', where '' can be '(', ')', or empty, determine if it can be valid.

Twist: The wildcard '' adds ambiguity—we must track possible states.

Approach: 1. Track the minimum and maximum possible open brackets:
- min_open: Smallest possible open brackets (treat '' as ')').
- max_open: Largest possible open brackets (treat '' as '('). 2. If max_open < 0 → Invalid (too many closing brackets). 3. If min_open > 0 → Invalid (unmatched opening brackets).

Code (Python):

def checkValidString(s: str) -> bool:

    min_open = max_open = 0

    for char in s:

        if char == '(':

            min_open += 1

            max_open += 1

        elif char == ')':

            min_open = max(min_open - 1, 0)

            max_open -= 1

        else:  # ''

            min_open = max(min_open - 1, 0)

            max_open += 1

        if max_open < 0:

            return False

    return min_open == 0

Complexity: - Time: O(n) (single pass). - Space: O(1) (no stack, just counters).

Why This Works: - Greedy tracking of possible open brackets avoids backtracking. - min_open and max_open bound the solution space.

Example 3 – Hard: Minimum Add to Make Parentheses Valid (LeetCode 921)

Problem: Given a string s of '(' and ')', return the minimum number of additions to make it valid.

Follow-up: Solve in O(n) time and O(1) space.

Approach: 1. Track unmatched opening and closing brackets:
- open_needed: Count of ')' needed to balance '('.
- close_needed: Count of '(' needed to balance ')'. 2. Iterate and update counters:
- '(' → open_needed += 1
- ')' → If open_needed > 0 → open_needed -= 1 (matched), else close_needed += 1.

Code (Python):

def minAddToMakeValid(s: str) -> int:

    open_needed = close_needed = 0

    for char in s:

        if char == '(':

            open_needed += 1

        else:

            if open_needed > 0:

                open_needed -= 1

            else:

                close_needed += 1

    return open_needed + close_needed

Complexity: - Time: O(n) (single pass). - Space: O(1) (constant extra space).

Why This Works: - Greedy counting ensures we only add the minimum required brackets. - No stack needed—just two counters.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. For Valid Parentheses, here’s your battle plan: 1. Edge Cases First: Odd length? Empty string? Handle them upfront. 2. Stack + Hash Map: Push opening brackets, pop on closing. Use a hash map to enforce correct pairs. 3. Early Termination: If you see a closing bracket with an empty stack, return False immediately. 4. Final Check: If the stack isn’t empty, there are unmatched opening brackets—return False. 5. Follow-ups: For wildcards or minimum additions, track counters instead of a stack.

Remember: This pattern tests your ability to handle LIFO logic and edge cases. Practice with '()[]{}', then try '()' and minimum additions. You’ve got this—now go crush that interview!

? FINAL TIPS

• Whiteboard First: Sketch the stack and hash map before coding.
• Test Edge Cases: "", "(", ")", "([)]", "([{}])".
• Time Yourself: Aim for <10 minutes for the basic problem.
• Explain Complexity: Always state O(n) time, O(n) space (or O(1) for follow-ups).

Now go solve it! ?