Valid Parentheses - Stack Pattern Guide

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

You are given a string s containing only characters ()[]{}. Return true if the string is valid.

Examples

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

🎯 Real-World Analogy

Plate Stack at a Restaurant

In a stack of plates, the last plate you place is the first one you remove. Bracket matching works exactly the same way: the most recently opened bracket must close first.

If a close bracket arrives that does not match the top of the stack, the order is broken.

💡 Key Insights

This is a strict LIFO problem -> stack is the natural structure.
Push opening brackets, validate on closing brackets.
If a closing bracket appears with empty stack, string is invalid.
After processing all chars, stack must be empty.

💻 Solution Approaches

Approach 1: Repeated String Replacement (Not Ideal)

Time: O(N²) worst-case | Space: O(N)

Repeatedly replace (), [], and {} until no changes. Works for simple cases but performs poorly.

Approach 2: Stack with Pair Map (Recommended)

Time: O(N) | Space: O(N)

Keep opening brackets on stack. On each closing bracket, pop and compare expected pair.

Python Implementation

          def is_valid(s: str) -> bool:
    """
    Validate parentheses/brackets/braces in proper nesting order.

    Time: O(N)
    Space: O(N)
    """
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack:
                return False
            top = stack.pop()
            if top != pairs[ch]:
                return False

    return len(stack) == 0
        

JavaScript Implementation

          function isValid(s) {
  /**
   * Time: O(N)
   * Space: O(N)
   */
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{',
  };

  const stack = [];

  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') {
      stack.push(ch);
    } else {
      if (stack.length === 0) return false;
      const top = stack.pop();
      if (top !== pairs[ch]) return false;
    }
  }

  return stack.length === 0;
}
        

🔍 Step-by-Step Walkthrough

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

            Read ( -> push -> stack: [(]
          
            Read [ -> push -> stack: [(, []
          
            Read { -> push -> stack: [(, [, {]
          
            Read } -> pop {, matches ✓
          
            Read ] -> pop [, matches ✓
          
            Read ) -> pop (, matches ✓
          
Stack empty at end -> valid

⚡ Complexity Analysis

Time Complexity: O(N)

Each character is pushed or popped at most once.
Map lookups and stack operations are constant time.

Space Complexity: O(N)

Worst case stores all openings in stack, e.g., "((((".
Pair map is constant size.

🔧 Edge Cases

Starts with closing bracket (e.g., ")(").
Odd-length string can never be valid.
All opening brackets with no closes.
Wrong nesting order: "([)]".

🧪 Test Cases

Case 1
"()[]{}" -> true

Case 2
"(]" -> false

Case 3
"([{}])" -> true

💼 Interview Tips

Explain why stack is the best-fit data structure before coding.
Call out fail-fast checks (if not stack on close).
Mention early optimization: odd length -> immediate false.
Discuss follow-up: handling arbitrary bracket types or stream input.

🎓 Key Takeaways

Bracket validation is a canonical stack pattern.
Matching must follow both type and order.
A clean pair map keeps logic readable.
Fail fast on impossible states to reduce bugs.

← Back to All Algorithms