101. Valid Parentheses

🔗 LeetCode Problem: 20. Valid Parentheses
📊 Difficulty: Easy
🏷️ Topics: Stack, String

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([])"
Output: true

Constraints: - 1 <= s.length <= 10^4 - s consists of parentheses only '()[]{}'.

---

🌟 ELI5: The Simple Idea!

Think of opening and closing doors:

Valid sequence:
  Open door A → Open door B → Close door B → Close door A
  (           [             ]               )  ✓

Invalid sequence:
  Open door A → Open door B → Close door A → Close door B
  (           [             )               ]  ✗

The MOST RECENT opened door must be closed FIRST!
This is LIFO = Stack!

Real-world analogy:

Like nesting boxes:
  Valid:
    Box1[ Box2{ Box3( ) } ]  ✓
    Each inner box closed before outer

  Invalid:
    Box1[ Box2{ Box3( ] ) }  ✗
    Closed Box1 before Box3!

---

🎨 Visual Understanding

Valid Example

Input: "({[]})"

Step-by-step with stack:

Char: '('
  Opening bracket → Push to stack
  Stack: ['(']

Char: '{'
  Opening bracket → Push to stack
  Stack: ['(', '{']

Char: '['
  Opening bracket → Push to stack
  Stack: ['(', '{', '[']

Char: ']'
  Closing bracket → Check top
  Top is '[' → Match! Pop
  Stack: ['(', '{']

Char: '}'
  Closing bracket → Check top
  Top is '{' → Match! Pop
  Stack: ['(']

Char: ')'
  Closing bracket → Check top
  Top is '(' → Match! Pop
  Stack: []

End: Stack empty → Valid! ✓

Invalid Example

Input: "([)]"

Step-by-step:

Char: '('
  Stack: ['(']

Char: '['
  Stack: ['(', '[']

Char: ')'
  Top is '[' → Expected ']' but got ')'
  Mismatch! → Invalid! ✗

---

🎯 Approach: Stack with HashMap ⭐

The Optimal Solution

Algorithm:

1. Create stack and mapping of closing → opening
2. For each character:
   - If opening bracket: push to stack
   - If closing bracket:
     - Check if stack is empty (no matching opening)
     - Pop and verify it matches
3. Return stack.isEmpty() (all matched)

Implementation

/**
 * Stack-based matching with HashMap
 * Time: O(n), Space: O(n)
 */
public boolean isValid(String s) {
    // Stack to track opening brackets
    Stack<Character> stack = new Stack<>();

    // Map closing brackets to their opening counterparts
    Map<Character, Character> pairs = new HashMap<>();
    pairs.put(')', '(');
    pairs.put('}', '{');
    pairs.put(']', '[');

    for (char c : s.toCharArray()) {
        if (pairs.containsKey(c)) {
            // Closing bracket
            if (stack.isEmpty()) {
                return false;  // No matching opening
            }

            if (stack.pop() != pairs.get(c)) {
                return false;  // Wrong opening bracket
            }
        } else {
            // Opening bracket
            stack.push(c);
        }
    }

    // All brackets must be matched
    return stack.isEmpty();
}

⏰ Time: O(n) - Single pass through string
💾 Space: O(n) - Stack stores up to n/2 brackets in worst case

Alternative (More Concise)

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(')');
        } else if (c == '{') {
            stack.push('}');
        } else if (c == '[') {
            stack.push(']');
        } else if (stack.isEmpty() || stack.pop() != c) {
            return false;
        }
    }

    return stack.isEmpty();
}

Clever trick: Push the EXPECTED closing bracket!

🔍 Super Detailed Dry Run

Example: s = "{[()]}"

Goal: Validate all brackets match correctly

═══════════════════════════════════════════════════════════════
Setup
═══════════════════════════════════════════════════════════════

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

═══════════════════════════════════════════════════════════════
Iteration 1: c = '{'
═══════════════════════════════════════════════════════════════

Is '{' in pairs (closing brackets)? No
Action: Opening bracket → Push to stack

Stack: ['{']

═══════════════════════════════════════════════════════════════
Iteration 2: c = '['
═══════════════════════════════════════════════════════════════

Is '[' in pairs? No
Action: Opening bracket → Push to stack

Stack: ['{', '[']

═══════════════════════════════════════════════════════════════
Iteration 3: c = '('
═══════════════════════════════════════════════════════════════

Is '(' in pairs? No
Action: Opening bracket → Push to stack

Stack: ['{', '[', '(']

═══════════════════════════════════════════════════════════════
Iteration 4: c = ')'
═══════════════════════════════════════════════════════════════

Is ')' in pairs? Yes (closing bracket)
Expected opening: pairs.get(')') = '('

Check: Is stack empty? No ✓
Pop from stack: '('
Match check: '(' == '('? Yes ✓

Stack: ['{', '[']

═══════════════════════════════════════════════════════════════
Iteration 5: c = ']'
═══════════════════════════════════════════════════════════════

Is ']' in pairs? Yes
Expected opening: pairs.get(']') = '['

Check: Is stack empty? No ✓
Pop from stack: '['
Match check: '[' == '['? Yes ✓

Stack: ['{']

═══════════════════════════════════════════════════════════════
Iteration 6: c = '}'
═══════════════════════════════════════════════════════════════

Is '}' in pairs? Yes
Expected opening: pairs.get('}') = '{'

Check: Is stack empty? No ✓
Pop from stack: '{'
Match check: '{' == '{'? Yes ✓

Stack: []

═══════════════════════════════════════════════════════════════
Final Check
═══════════════════════════════════════════════════════════════

All characters processed
Is stack empty? Yes ✓

Return: true

Result: Valid parentheses! ✓

Example 2: s = "([)]" (Invalid)

═══════════════════════════════════════════════════════════════
Process
═══════════════════════════════════════════════════════════════

c = '(': stack = ['(']
c = '[': stack = ['(', '[']
c = ')': Pop '[', Expected '(' but got '['
         '[' != '(' ✗

Return: false

Result: Invalid! ✗

Example 3: s = "((" (Invalid)

═══════════════════════════════════════════════════════════════
Process
═══════════════════════════════════════════════════════════════

c = '(': stack = ['(']
c = '(': stack = ['(', '(']

End of string
Is stack empty? No ✗

Return: false

Result: Invalid (unmatched opening brackets)! ✗

Example 4: s = "))" (Invalid)

═══════════════════════════════════════════════════════════════
Process
═══════════════════════════════════════════════════════════════

c = ')': Is stack empty? Yes ✗

Return: false immediately

Result: Invalid (no matching opening)! ✗

---

🎯 Why This Solution Works

The Stack Insight

Why Stack?
  - Most recent opening must match first closing
  - This is LIFO (Last In, First Out)
  - Stack naturally provides LIFO

Example:
  Input: "( [ ] )"

  After "(": stack = ['(']
  After "[": stack = ['(', '[']
           Must close '[' before '('

  When "]": Pop '[' (most recent)
  When ")": Pop '(' (next most recent)

Three Conditions for Valid

1. Every closing has a matching opening
   → Stack must not be empty when closing comes

2. Correct type of bracket
   → Popped opening must match closing

3. All brackets paired
   → Stack must be empty at end

Why HashMap?

Map<Character, Character> pairs = {
    ')': '(',
    '}': '{',
    ']': '['
}

Advantages:
  ✓ Easy to check if closing bracket
  ✓ Get expected opening in O(1)
  ✓ Extensible (easy to add new bracket types)
  ✓ Clean code

---

🎯 Alternative Approach: Push Expected Closing

The Clever Trick

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        // Push the EXPECTED closing bracket
        if (c == '(') stack.push(')');
        else if (c == '{') stack.push('}');
        else if (c == '[') stack.push(']');

        // Check if closing matches expected
        else if (stack.isEmpty() || stack.pop() != c) {
            return false;
        }
    }

    return stack.isEmpty();
}

Why this works:

Opening '(' → Push what we EXPECT to see: ')'
Closing ')' → Check if it matches top

Example: "({[]})"

c = '(': stack = [')']
c = '{': stack = [')', '}']
c = '[': stack = [')', '}', ']']
c = ']': Pop ']', matches c ✓, stack = [')', '}']
c = '}': Pop '}', matches c ✓, stack = [')']
c = ')': Pop ')', matches c ✓, stack = []

Clean! ✓

---

⚠️ Common Mistakes

Mistake 1: Not checking empty stack before pop

// ❌ WRONG - EmptyStackException for ")"
if (stack.pop() != pairs.get(c)) {
    return false;
}

// ✓ CORRECT - Check first
if (stack.isEmpty()) {
    return false;
}
if (stack.pop() != pairs.get(c)) {
    return false;
}

Mistake 2: Forgetting to check stack at end

// ❌ WRONG - Accepts "((" as valid
return true;

// ✓ CORRECT - All must be matched
return stack.isEmpty();

Mistake 3: Wrong bracket matching logic

// ❌ WRONG - Checks if closing == opening
if (stack.pop() == c) {  // '(' == ')'? Never true!

// ✓ CORRECT - Use map or push expected
if (stack.pop() != pairs.get(c)) {

Mistake 4: Using wrong data structure

// ❌ WRONG - Need LIFO, not FIFO
Queue<Character> queue = new LinkedList<>();

// ✓ CORRECT - Stack for LIFO
Stack<Character> stack = new Stack<>();

Mistake 5: Not handling all bracket types

// ❌ WRONG - Only handles ()
if (c == '(') stack.push(c);

// ✓ CORRECT - Handle all three types
if (c == '(' || c == '{' || c == '[') {
    stack.push(c);
}

---

🎯 Pattern Recognition

Problem Type: Matching Pairs (Parentheses)
Core Pattern: Stack Pattern 1 - Matching Pairs

When to Apply:
✓ Validate matching brackets/parentheses
✓ Check balanced delimiters
✓ Verify proper nesting
✓ Match opening/closing tags

Recognition Keywords:
- "valid"
- "balanced"
- "parentheses"
- "brackets"
- "matching"
- "proper order"

Similar Problems:
- Generate Parentheses (LC 22)
- Minimum Add to Make Valid (LC 921)
- Longest Valid Parentheses (LC 32) - Hard
- Remove Invalid Parentheses (LC 301) - Hard

Key Components:
┌────────────────────────────────────────────┐
│ Stack: Track opening brackets             │
│ Push: When see opening bracket            │
│ Pop: When see closing bracket             │
│ Validate: Pop matches closing type        │
│ Final: Stack must be empty                │
│ Time: O(n), Space: O(n)                   │
└────────────────────────────────────────────┘

---

🧠 Interview Strategy

Step 1: "I recognize this as a matching pairs problem"
Step 2: "I'll use a stack to track opening brackets"
Step 3: "Push opening, pop and match closing"

Key Points to Mention:
- Stack provides LIFO for most recent matching
- Three checks: empty stack, correct type, final empty
- HashMap maps closing to opening brackets
- Alternative: push expected closing
- Time: O(n), Space: O(n)

Walk Through Example:
"For '({[]})'':
 '(' → Push to stack
 '{' → Push to stack
 '[' → Push to stack
 ']' → Pop '[', matches ✓
 '}' → Pop '{', matches ✓
 ')' → Pop '(', matches ✓
 Stack empty → Valid!"

Why Stack:
"Need to match most recent opening bracket.
 This is LIFO behavior = Stack.
 If we used queue (FIFO), we'd match oldest
 opening bracket, which is wrong."

Edge Cases to Mention:
✓ Empty string → valid (edge case depends on requirement)
✓ Only opening brackets → invalid (stack not empty)
✓ Only closing brackets → invalid (empty stack on close)
✓ Wrong order → invalid (mismatch)
✓ Single character → invalid (can't be matched)

---

📝 Quick Revision Notes

🎯 Core Concept:

Valid Parentheses: Use stack to track opening brackets. Push opening brackets ( { [. When see closing ) } ], check stack not empty and pop matches. At end, stack must be empty (all matched). Use HashMap to map closing→opening for clean code.

⚡ Quick Implementation:

import java.util.HashMap;
import java.util.Stack;

class Solution {
  public boolean isValid(String s) {
    // // Approach 1 - using hashmap
    // // Store corresponding chars.
    // HashMap<Character, Character> map = new HashMap<>();
    // map.put(')', '(');
    // map.put(']', '[');
    // map.put('}', '{');

    // Stack<Character> stack = new Stack<>();
    // for(char c : s.toCharArray()) {
    //   if(!map.containsKey(c)) {
    //     stack.push(c);
    //   } else {
    //     if(stack.pop() != map.get(c)) {
    //       return false;
    //     }
    //   }
    // }

    // return stack.isEmpty();

    // Approach 2 - using stack alone (little clever)
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()) {
      switch (c) {
        case '(':
          stack.push(')');
          break;

        case '[':
          stack.push(']');
          break;

        case '{':
          stack.push('}');
          break;

        default:
          if(stack.isEmpty() || stack.pop() != c) {
            return false;
          }
          break;
      }
    }

    return stack.isEmpty();
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out.println(s.isValid("()"));
    System.out.println(s.isValid("()[]{}"));
    System.out.println(s.isValid(""));
    System.out.println(s.isValid("("));
    System.out.println(s.isValid("(]"));
  }
}

🔑 Key Insights:

• Pattern: Stack Pattern 1 (Matching Pairs)
• LIFO: Most recent opening matches first closing
• Three checks: empty before pop, correct type, empty at end
• HashMap: Clean way to map closing→opening
• Alternative: Push expected closing bracket
• Time: O(n), Space: O(n) ✓

🎪 Memory Aid:

"Open pushes, close pops and matches, end checks empty!"
"Push opening, pop matching closing, verify empty!" ✨

⚠️ Critical Checks:

Three essential checks:

1. Before popping:
   if (stack.isEmpty()) return false;

2. After popping:
   if (popped != expected) return false;

3. At the end:
   return stack.isEmpty();

Miss any of these → Wrong answer!

---

🧪 Edge Cases

Case 1: Empty string

Input: s = ""
Output: true (or depends on requirement)
Handled: Loop doesn't run, stack empty

Case 2: Single character

Input: s = "("
Output: false
Handled: Stack not empty at end

Case 3: Only opening

Input: s = "((("
Output: false
Handled: Stack not empty at end

Case 4: Only closing

Input: s = ")))"
Output: false
Handled: Stack empty on first pop attempt

Case 5: Wrong order

Input: s = "([)]"
Output: false
Handled: Pop '[' but expect '(' for ')'

Case 6: Nested valid

Input: s = "{[()]}"
Output: true
Handled: All brackets match in correct order

All handled perfectly! ✓

---

🎓 Complexity Analysis

Time Complexity: O(n)

Single pass through string:
  for (char c : s.toCharArray())  // n iterations

Per iteration:
  - HashMap lookup: O(1)
  - Stack push: O(1)
  - Stack pop: O(1)

Total: O(n) ✓

Space Complexity: O(n)

Stack space:
  Worst case: all opening brackets
  Example: "((((("
  Stack stores n/2 elements

HashMap space:
  Only 3 entries (constant)
  O(1)

Total: O(n) for stack ✓

---

🔄 Variations & Extensions

Extension 1: Custom Bracket Types

// Easy to extend!
Map<Character, Character> pairs = Map.of(
    ')', '(',
    '}', '{',
    ']', '[',
    '>', '<',  // Add custom
    '»', '«'   // Add custom
);

Extension 2: With Other Characters

// Ignore non-bracket characters
for (char c : s.toCharArray()) {
    if (c == '(' || c == '{' || c == '[') {
        stack.push(c);
    } else if (c == ')' || c == '}' || c == ']') {
        // Check matching
    }
    // else: ignore other characters
}

Extension 3: Return Error Position

public int findInvalidPosition(String s) {
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        // ... matching logic
        if (invalid) {
            return i;  // Return position
        }
    }

    return stack.isEmpty() ? -1 : stack.size();
}

---

📚 Related Problems

Same Pattern (Easier): - Remove Outermost Parentheses (LC 1021)

Same Pattern (Harder): - Generate Parentheses (LC 22) - Generate valid combinations - Minimum Add to Make Valid (LC 921) - Count missing brackets - Valid Parenthesis String (LC 678) - With wildcards

Advanced: - Longest Valid Parentheses (LC 32) - Hard, find longest valid - Remove Invalid Parentheses (LC 301) - Hard, BFS/DFS

---

Happy practicing! 🎯

Note: This is THE foundational stack problem! Master this and you understand: (1) LIFO behavior, (2) matching pairs pattern, (3) stack usage, (4) validation logic. This pattern appears in dozens of problems. It's asked at Amazon, Meta, Google, Apple constantly. The "push opening, pop matching closing" pattern is fundamental! 💪✨