Valid Parentheses

• Difficulty: Easy
• Topics: String, Stack
• Link: https://leetcode.com/problems/valid-parentheses/

Problem Description

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 <= 104
• s consists of parentheses only '()[]{}'.

Solution

1. Problem Deconstruction

Technical Description

Given a string s of length n (1 ≤ n ≤ 10⁴) comprising exclusively the characters ‘(’, ‘)’, ‘[’, ‘]’, ‘{’, ‘}’, determine if s satisfies:

1. Type Matching: Every opening bracket ( ‘(’, ‘[’, ‘{’ ) must be closed by a bracket of the identical type.
2. Order Preservation: The closing bracket for an opening bracket must appear in the reverse order of opening. Formally, if bracket b opens after bracket a, b must close before a.
3. Completeness: All closing brackets must have a corresponding open bracket.

Beginner Description

Imagine arranging nested boxes:

• Each opening bracket ( ‘(’, ‘[’, ‘{’ ) starts a new box.
• Each closing bracket ( ‘)’, ‘]’, ‘}’ ) closes the most recently opened box.
• Rules:
  • Boxes must be closed with the correct lid (e.g., a round box needs a round lid).
  • Inner boxes must be closed before outer boxes.
  • No extra lids or missing boxes allowed.
    The string is “valid” if all boxes are perfectly closed without leftovers.

Mathematical Description

Let s = c₁c₂...cₙ where cᵢ ∈ Σ = {'(', ')', '[', ']', '{', '}'}.
Define:

• Mapping function f: Σ → Σ with f('(') = ')', f('[') = ']', f('{') = '}'.
• Opening set O = {'(', '[', '{'}.
• Stack S (initially empty).
  For i = 1 to n:
  • If cᵢ ∈ O, push cᵢ onto S.
  • Else, if S is non-empty and f(top(S)) = cᵢ, pop S. Else, invalid.
    String is valid iff S = ∅ after processing.

Constraint Analysis

• 1 ≤ n ≤ 10⁴:
  • Rules out O(n²) brute-force (e.g., 10⁸ operations worst-case).
  • Mandates O(n) or O(n log n) solutions.
  • Edge: Single-character strings (e.g., "[") are invalid (odd length).
• s contains only ‘()[]{}’:
  • No input sanitation needed.
  • Edge: All-opening (e.g., "(([") or all-closing (e.g., "])}") strings.
• Hidden Edges:
  • Odd-length strings: Automatically invalid (e.g., "()[").
  • Premature closing: Closing bracket before any opener (e.g., "])").
  • Interleaved brackets: Valid type count but invalid order (e.g., "([)]").

---

2. Intuition Scaffolding

Analogies

1. Real-World (Stack of Books):
   • Opening bracket: Place a book on a pile.
   • Closing bracket: Remove the top book only if its cover matches.
   • Invalid if: Wrong cover, removal from empty pile, books left.
2. Gaming (RPG Quest Chain):
   • Start quest A (opening bracket).
   • Start quest B before completing A.
   • Must complete B (closing bracket) before A.
   • Invalid: Complete unstarted quest or leave quests incomplete.
3. Math (Function Composition):
   • Let g ∘ f denote applying f then g.
   • Bracketing (f ∘ g) ∘ h is valid; (f ∘ g) ∘ h) is invalid (unmatched )).

Common Pitfalls

1. Ignoring Order:
   • Incorrect: Count each bracket type independently. Fails for "([)]" (counts balanced but order invalid).
2. Ignoring Stack Empty Check:
   • Crash for closing without opener (e.g., "]").
3. Assuming Even-Length Suffices:
   • Even length doesn’t guarantee validity (e.g., "[[))").
4. Incorrect Mapping:
   • E.g., Map ')' to '[' → fails "()".
5. Not Final-Stack Check:
   • Returns true for "(" (unmatched opener).

---

3. Approach Encyclopedia

1. Brute Force (Recursive Elimination)

Pseudocode:

while any bracket pair exists:  
    replace "()", "[]", "{}" with ""  
return s == ""  

Complexity Proof:

• Time: Worst-case O(n²).
  • Example: "(((...)))" (deeply nested).
  • Each iteration removes one pair (O(n) pairs), scanning O(n) per iteration → O(n²).
• Space: O(n) (string storage).

Visualization:

s = "([]){}"  
Step 1: Remove "[]" → "(){}"  
Step 2: Remove "()" → "{}"  
Step 3: Remove "{}" → "" → valid.  

2. Stack (Optimal)

Pseudocode:

if n is odd: return False  
stack = []  
map = {')': '(', ']': '[', '}': '{'}  
for c in s:  
    if c in map.values: stack.push(c)  
    else:  
        if stack.empty or map[c] != stack.pop():  
            return False  
return stack.empty  

Complexity Proof:

• Time: O(n). Each operation (push/pop) is O(1), traversed once.
• Space: O(n) (stack stores ≤ n/2 elements worst-case).

Visualization:

s = "([])"  
Step 1: '(' → stack = ['(']  
Step 2: '[' → stack = ['(', '[']  
Step 3: ']' → pop '[' → matches ']' → stack = ['(']  
Step 4: ')' → pop '(' → matches ')' → stack empty → valid.  

---

4. Code Deep Dive

Optimal Code (Python):

def isValid(s: str) -> bool:  
    if len(s) % 2 != 0:  # Early rejection for odd length  
        return False  
    stack = []  
    mapping = {')': '(', ']': '[', '}': '{'}  # Closing → opening map  
    for char in s:  
        if char in mapping.values():  # Opening bracket  
            stack.append(char)  
        elif char in mapping:  # Closing bracket  
            if not stack or mapping[char] != stack.pop():  
                return False  
    return not stack  # True if stack empty  

Line-by-Line Analysis:

1. len(s) % 2 != 0:
   • What: Early check for odd-length strings.
   • Why: Odd length guarantees imbalance.
   • How: Returns False immediately.
2. stack = []:
   • What: LIFO structure to track openers.
   • Why: Enforces “last opened, first closed” rule.
3. mapping = ...:
   • What: Dictionary mapping closers to openers.
   • Why: Efficiently check type matching.
4. if char in mapping.values():
   • What: Detects opening brackets.
   • Why: Push to stack for future matching.
5. elif char in mapping:
   • What: Handles closing brackets.
   • Why: Validate against the last opener.
6. not stack or mapping[char] != stack.pop():
   • What: Checks: (a) stack non-empty, (b) top matches closer.
   • Why: Prevents popping from empty stack or mismatched brackets.
7. return not stack:
   • What: Final stack must be empty.
   • Why: Unmatched openers invalidate the string.

Edge Case Handling:

• Example 1 ("()"):
  • n=2 (even) → stack pushes ‘(’ → pops for ‘)’ → stack empty → True.
• Example 3 ("(]"):
  • Pushes ‘(’ → encounters ‘]’ → mapping[']'] = '[' ≠ stack.pop()=‘(’ → False.
• All-Closing ("]]]"):
  • n=3 (odd) → early False.
• Unmatched Opener ("("):
  • n=1 → early False.

---

5. Complexity War Room

Hardware-Aware Analysis:

• Time: O(n) → 10⁴ operations trivial (<1 ms in Python).
• Space: Worst-case stack size = 5000 elements (n=10⁴).
  • Each char: 48 bytes (Python str overhead) → 5000 × 48 B ≈ 240 KB.
  • Fits in CPU L3 cache (MBs), negligible for modern systems.

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(n)	High	❌ (Fails large n)
Stack (Optimal)	O(n)	O(n)	High	✅ (Optimal)
Stack + Early	O(n)	O(n)	High	✅ (Best Practice)

---

6. Pro Mode Extras

Variants

1. Leetcode 678 (Wildcard Parentheses):
   • s contains ‘*’ treatable as ‘(’, ‘)’ or empty.
   • Solution: Track min/max possible open counts.
2. Leetcode 32 (Longest Valid Parentheses):
   • Find longest valid substring.
   • Solution: DP or stack with indices.
3. Multi-Type with Escapes:
   • Support escape characters (e.g., "\(" is literal).
   • Solution: State machine with escape flags.

Interview Cheat Sheet

• First Steps:
  1. Check length parity.
  2. Declare stack and bracket mapping.
• Must-Mention:
  • “Stack ensures LIFO order for bracket matching.”
  • “Early odd-length check optimizes half the cases.”
• Edge Tests:
  • "[" (unmatched opener), "]" (unmatched closer), "([)]" (interleaved).
• Time/Space: Always state first: “O(n) time, O(n) space.”