0020. Valid Parentheses¶

Table of Contents¶

1. Problem
2. Problem Breakdown
3. Approach 1: Stack
4. Approach 2: Replace Pairs
5. Complexity Comparison
6. Edge Cases
7. Common Mistakes
8. Related Problems
9. Visual Animation

Problem¶

Leetcode	20. Valid Parentheses
Difficulty	Easy
Tags	String, Stack

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.

Examples¶

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 '()[]{}'

Problem Breakdown¶

1. What is being asked?¶

Determine whether a string of brackets is well-formed -- every opening bracket has a matching closing bracket of the same type, and they are properly nested.

2. What is the input?¶

Important observations about the input: - The string contains only bracket characters (no letters, digits, etc.) - The string can be empty (length >= 1 per constraints, but logically empty = valid) - Multiple bracket types can be intermixed - Brackets can be nested to any depth

3. What is the output?¶

• A boolean value: true if the string is valid, false otherwise
• Valid means all three conditions are satisfied simultaneously

4. Constraints analysis¶

5. Step-by-step example analysis¶

Example 1: s = "()"¶

Initial state: s = "()"

Character '(' -- opening bracket, push onto stack
  Stack: ['(']

Character ')' -- closing bracket, matches top '(' -- pop
  Stack: []

Stack is empty -> true

Example 2: s = "(]"¶

Initial state: s = "(]"

Character '(' -- opening bracket, push onto stack
  Stack: ['(']

Character ']' -- closing bracket, top is '(' but expected '[' -- MISMATCH!
  return false

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

Initial state: s = "{[()]}"

Character '{' -> push    Stack: ['{']
Character '[' -> push    Stack: ['{', '[']
Character '(' -> push    Stack: ['{', '[', '(']
Character ')' -> match ( Stack: ['{', '[']
Character ']' -> match [ Stack: ['{']
Character '}' -> match { Stack: []

Stack is empty -> true

6. Key Observations¶

1. LIFO order -- The most recently opened bracket must be closed first. This is exactly how a stack works.
2. Bracket matching -- Each closing bracket must match the type of the most recent unmatched opening bracket.
3. Even length -- A valid string must have even length (each open has a close).
4. Stack empty at end -- If the stack is not empty after processing all characters, there are unmatched opening brackets.

7. Pattern identification¶

Chosen pattern: Stack Reason: The problem requires matching brackets in LIFO order, which is the fundamental property of a stack.

Approach 1: Stack¶

Thought process¶

Use a stack to track opening brackets. When we encounter a closing bracket, check if it matches the top of the stack. If it matches, pop the stack. If not, the string is invalid. At the end, the stack must be empty for the string to be valid.

Algorithm (step-by-step)¶

1. Create an empty stack
2. Create a mapping: closing bracket -> corresponding opening bracket
3. Iterate through each character in the string:
4. If it's an opening bracket ((, [, {): push onto stack
5. If it's a closing bracket:
   • If stack is empty -> return false
   • If top of stack != matching opening bracket -> return false
   • Otherwise, pop the top of the stack
6. Return true if the stack is empty, false otherwise

Pseudocode¶

function isValid(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for ch in s:
        if ch is opening bracket:
            stack.push(ch)
        else:
            if stack is empty or stack.top != matching[ch]:
                return false
            stack.pop()

    return stack is empty

Complexity¶

Implementation¶

Go¶

func isValid(s string) bool {
    stack := []byte{}
    matching := map[byte]byte{')': '(', ']': '[', '}': '{'}

    for i := 0; i < len(s); i++ {
        ch := s[i]
        if ch == '(' || ch == '[' || ch == '{' {
            stack = append(stack, ch)
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != matching[ch] {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

Java¶

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> matching = Map.of(
            ')', '(', ']', '[', '}', '{'
        );

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty() || !stack.peek().equals(matching.get(ch))) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

Python¶

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matching = {')': '(', ']': '[', '}': '{'}

        for ch in s:
            if ch in '([{':
                stack.append(ch)
            else:
                if not stack or stack[-1] != matching[ch]:
                    return False
                stack.pop()

        return len(stack) == 0

Dry Run¶

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

stack = []

Step 1: ch='{', opening -> push
        stack = ['{']

Step 2: ch='[', opening -> push
        stack = ['{', '[']

Step 3: ch='(', opening -> push
        stack = ['{', '[', '(']

Step 4: ch=')', closing, matching[')']='('
        stack top = '(' == '(' -> match, pop
        stack = ['{', '[']

Step 5: ch=']', closing, matching[']']='['
        stack top = '[' == '[' -> match, pop
        stack = ['{']

Step 6: ch='}', closing, matching['}']='{'
        stack top = '{' == '{' -> match, pop
        stack = []

Stack is empty -> return true

Input: s = "([)]"

stack = []

Step 1: ch='(', opening -> push
        stack = ['(']

Step 2: ch='[', opening -> push
        stack = ['(', '[']

Step 3: ch=')', closing, matching[')']='('
        stack top = '[' != '(' -> MISMATCH!
        return false

Approach 2: Replace Pairs¶

Thought process¶

Repeatedly remove all adjacent valid pairs (), [], {} from the string. If the string becomes empty, it was valid. Otherwise, it's invalid. This is simpler to understand but much slower.

Algorithm (step-by-step)¶

1. Repeat until no more replacements can be made:
2. Replace all occurrences of () with ""
3. Replace all occurrences of [] with ""
4. Replace all occurrences of {} with ""
5. If the string is empty -> return true
6. Otherwise -> return false

Pseudocode¶

function isValid(s):
    while true:
        new_s = s.replace("()", "").replace("[]", "").replace("{}", "")
        if new_s == s:
            break  // no more replacements possible
        s = new_s
    return s is empty

Complexity¶

Implementation¶

Go¶

import "strings"

func isValid(s string) bool {
    for {
        newS := strings.ReplaceAll(s, "()", "")
        newS = strings.ReplaceAll(newS, "[]", "")
        newS = strings.ReplaceAll(newS, "{}", "")
        if newS == s {
            break
        }
        s = newS
    }
    return len(s) == 0
}

Java¶

class Solution {
    public boolean isValid(String s) {
        while (true) {
            String newS = s.replace("()", "")
                           .replace("[]", "")
                           .replace("{}", "");
            if (newS.equals(s)) break;
            s = newS;
        }
        return s.isEmpty();
    }
}

Python¶

class Solution:
    def isValid(self, s: str) -> bool:
        while True:
            new_s = s.replace("()", "").replace("[]", "").replace("{}", "")
            if new_s == s:
                break
            s = new_s
        return len(s) == 0

Dry Run¶

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

Pass 1: replace "()" -> "{[]}"
         replace "[]" -> "{}"
         replace "{}" -> ""
         s changed: "{[()]}" -> ""

s is empty -> return true

Input: s = "([)]"

Pass 1: replace "()" -> "([)]" (no "()" found)
         replace "[]" -> "([)]" (no "[]" found)
         replace "{}" -> "([)]" (no "{}" found)
         s unchanged -> break

s = "([)]" is not empty -> return false

Complexity Comparison¶

Which solution to choose?¶

• In an interview: Approach 1 (Stack) -- demonstrates understanding of data structures
• In production: Approach 1 -- optimal time complexity
• On Leetcode: Approach 1 -- best Time Complexity
• For learning: Both -- Approach 2 helps build intuition, Approach 1 teaches the Stack pattern

Edge Cases¶

Common Mistakes¶

Mistake 1: Forgetting to check if stack is empty before popping¶

# WRONG -- stack[-1] throws IndexError if stack is empty
for ch in s:
    if ch in '([{':
        stack.append(ch)
    else:
        if stack[-1] != matching[ch]:  # crash if stack is empty!
            return False
        stack.pop()

# CORRECT -- check stack is not empty first
for ch in s:
    if ch in '([{':
        stack.append(ch)
    else:
        if not stack or stack[-1] != matching[ch]:
            return False
        stack.pop()

Reason: Input like "]" has a closing bracket with nothing on the stack.

Mistake 2: Returning true immediately when a match is found¶

# WRONG -- returns true on first match, ignoring remaining characters
if stack and stack[-1] == matching[ch]:
    stack.pop()
    return True  # premature!

# CORRECT -- process all characters, then check if stack is empty
return len(stack) == 0

Reason: "()(" has a valid pair but the string is still invalid.

Mistake 3: Forgetting to check stack is empty at the end¶

# WRONG -- doesn't check for unmatched opening brackets
for ch in s:
    if ch in '([{':
        stack.append(ch)
    else:
        if not stack or stack[-1] != matching[ch]:
            return False
        stack.pop()
return True  # what if stack still has elements?

# CORRECT -- check stack is empty
return len(stack) == 0

Reason: "((" processes without errors but leaves unmatched brackets on the stack.

Mistake 4: Using a counter instead of a stack¶

# WRONG -- counter only works for one bracket type
count = 0
for ch in s:
    if ch == '(':
        count += 1
    elif ch == ')':
        count -= 1
# This doesn't handle multiple bracket types or nesting order

# CORRECT -- use a stack to track bracket types

Reason: A counter cannot distinguish between "([])" (valid) and "([)]" (invalid).

Related Problems¶

#	Problem	Difficulty	Similarity
1	22. Generate Parentheses	Medium	Generate all valid combinations of parentheses
2	32. Longest Valid Parentheses	Hard	Find the longest valid substring
3	71. Simplify Path	Medium	Stack-based string processing
4	150. Evaluate Reverse Polish Notation	Medium	Stack-based evaluation
5	1249. Minimum Remove to Make Valid Parentheses	Medium	Remove minimum brackets to make valid

Visual Animation¶

Interactive animation: animation.html

In the animation: - Stack tab -- character-by-character processing with stack visualization - Replace Pairs tab -- repeatedly removes matching pairs until string is empty or unchanged