20. Valid Parentheses (Easy)

Problem

Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', determine if the input is valid. An input is valid if every open bracket is closed by the same type in the correct order.

Example

s = "()" → true
s = "()[]{}" → true
s = "(]" → false
s = "([)]" → false

LeetCode 20 · Link · Easy

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, repeated replacement

Repeatedly remove innermost pairs ("()", "[]", "{}") until the string stops changing. Valid iff the final string is empty.

def is_valid(s: str) -> bool:
    while "()" in s or "[]" in s or "{}" in s:           # L1: O(n) scan per iteration
        s = s.replace("()", "").replace("[]", "").replace("{}", "")  # L2: O(n) per replace
    return s == ""                                        # L3: O(n) comparison

function isValid(s: string): boolean {
    while (s.includes('()') || s.includes('[]') || s.includes('{}')) {  // L1: O(n) scan
        s = s.replace('()', '').replace('[]', '').replace('{}', '');     // L2: O(n) per replace
    }
    return s === '';                                                      // L3: O(n) comparison
}

func isValid(s string) bool {
    for strings.Contains(s, "()") || strings.Contains(s, "[]") || strings.Contains(s, "{}") {
        s = strings.ReplaceAll(s, "()", "")
        s = strings.ReplaceAll(s, "[]", "")
        s = strings.ReplaceAll(s, "{}", "")
    }
    return s == ""
}

final class Solution {
    func isValid(_ s: String) -> Bool {
        var remaining = Array(s)
        while true {
            var next: [Character] = []
            var removed = false
            var index = 0
            while index < remaining.count {
                if index + 1 < remaining.count && isPair(remaining[index], remaining[index + 1]) {
                    removed = true
                    index += 2
                } else {
                    next.append(remaining[index])
                    index += 1
                }
            }
            if !removed { return next.isEmpty }
            remaining = next
        }
    }

    private func isPair(_ opening: Character, _ closing: Character) -> Bool {
        (opening == "(" && closing == ")") ||
            (opening == "[" && closing == "]") ||
            (opening == "{" && closing == "}")
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (scan for pairs)	$O(n)$	up to n/2	$O(n²)$ ← dominates
L2 (three replaces)	$O(n)$ each	up to n/2	$O(n²)$ ← dominates
L3 (final check)	$O(n)$	1	$O(n)$

Each pass removes at least one pair and shrinks the string by 2. Up to n/2 passes, each $O(n)$ , gives $O(n²)$ total.

Complexity

Time: $O(n²)$ , driven by L1/L2 (up to n/2 passes, each $O(n)$ ).
Space: $O(n)$ for each intermediate string.

Cute but genuinely quadratic. Shows the intuition (innermost pairs cancel) without the optimal representation.

Approach 2: Stack with if/elif chain

Push opens; on a close, pop and verify the types match.

def is_valid(s: str) -> bool:
    stack = []                                 # L1: O(1) empty stack
    for ch in s:                               # L2: n iterations
        if ch in "([{":                        # L3: O(1) set-like check
            stack.append(ch)                   # L4: O(1) push
        else:
            if not stack:                      # L5: O(1) empty check
                return False
            top = stack.pop()                  # L6: O(1) pop
            if (ch == ")" and top != "(") or \
               (ch == "]" and top != "[") or \
               (ch == "}" and top != "{"):     # L7: O(1) type check
                return False
    return not stack                           # L8: O(1) all opens matched

function isValid(s: string): boolean {
    const stack: string[] = [];                        // L1: O(1) empty stack
    for (const ch of s) {                             // L2: n iterations
        if ('([{'.includes(ch)) {                     // L3: O(1) check
            stack.push(ch);                           // L4: O(1) push
        } else {
            if (!stack.length) return false;          // L5: O(1) empty check
            const top = stack.pop()!;                 // L6: O(1) pop
            if ((ch === ')' && top !== '(') ||
                (ch === ']' && top !== '[') ||
                (ch === '}' && top !== '{')) return false; // L7: O(1) type check
        }
    }
    return stack.length === 0;                        // L8: O(1) all opens matched
}

func isValid(s string) bool {
    stack := []byte{}                          // L1: O(1) empty stack
    for i := 0; i < len(s); i++ {             // L2: n iterations
        ch := s[i]
        if ch == '(' || ch == '[' || ch == '{' { // L3: O(1) check
            stack = append(stack, ch)          // L4: O(1) push
        } else {
            if len(stack) == 0 { return false } // L5: O(1) empty check
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]       // L6: O(1) pop
            if (ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{') {    // L7: O(1) type check
                return false
            }
        }
    }
    return len(stack) == 0                     // L8: O(1) all opens matched
}

final class Solution {
    func isValid(_ s: String) -> Bool {
        var stack: [Character] = []
        for character in s {
            if character == "(" || character == "[" || character == "{" {
                stack.append(character)
            } else {
                guard let opening = stack.popLast() else { return false }
                if character == ")" && opening != "(" { return false }
                if character == "]" && opening != "[" { return false }
                if character == "}" && opening != "{" { return false }
            }
        }
        return stack.isEmpty
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n	$O(n)$
L3-L7 (per-char work)	$O(1)$	n	$O(n)$ ← dominates
L8 (final check)	$O(1)$	1	$O(1)$

Each character is pushed or popped exactly once.

Complexity

Time: $O(n)$ , driven by L3-L7 (one push or pop per character).
Space: $O(n)$ for the stack (at most n/2 open brackets).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Stack with a pair-map (cleanest)

Replace the if/elif chain with a dictionary mapping closers to their matching openers.

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}     # L1: O(1) constant dict
    stack = []                                  # L2: O(1)
    for ch in s:                                # L3: n iterations
        if ch in pairs.values():               # L4: O(1) check (set of 3)
            stack.append(ch)                   # L5: O(1) push
        else:
            if not stack or stack.pop() != pairs[ch]:  # L6: O(1) pop + lookup
                return False
    return not stack                            # L7: O(1)

function isValid(s: string): boolean {
    const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }; // L1: O(1) dict
    const stack: string[] = [];                                              // L2: O(1)
    for (const ch of s) {                                                    // L3: n iterations
        if (Object.values(pairs).includes(ch)) {                             // L4: O(1) check
            stack.push(ch);                                                  // L5: O(1) push
        } else {
            if (!stack.length || stack.pop() !== pairs[ch]) return false;    // L6: O(1) pop+lookup
        }
    }
    return stack.length === 0;                                               // L7: O(1)
}

func isValid(s string) bool {
    pairs := map[byte]byte{')': '(', ']': '[', '}': '{'} // L1: O(1) map
    stack := []byte{}                                      // L2: O(1)
    for i := 0; i < len(s); i++ {                         // L3: n iterations
        ch := s[i]
        if ch == '(' || ch == '[' || ch == '{' {           // L4: O(1) check
            stack = append(stack, ch)                      // L5: O(1) push
        } else {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] { // L6: O(1) pop+lookup
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0                                 // L7: O(1)
}

final class Solution {
    func isValid(_ s: String) -> Bool {
        let openingForClosing: [Character: Character] = [")": "(", "]": "[", "}": "{"]
        var stack: [Character] = []
        for character in s {
            if let expected = openingForClosing[character] {
                guard stack.popLast() == expected else { return false }
            } else {
                stack.append(character)
            }
        }
        return stack.isEmpty
    }
}

Where the time goes, line by line

Variables: n = len(s).

Line	Per-call cost	Times executed	Contribution
L1-L2 (init)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$	n	$O(n)$
L4-L6 (per-char: push or pop+check)	$O(1)$	n	$O(n)$ ← dominates
L7 (final check)	$O(1)$	1	$O(1)$

Same $O(n)$ work, but the pair-map removes all branching.

Complexity

Time: $O(n)$ , driven by L4-L6 (one push or pop+check per character).
Space: $O(n)$ for the stack.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

How to recognize this pattern

The signal: “correct order.” The problem does not ask whether counts balance. It asks whether each closer matches the most recently opened bracket. Most recent = last in, first out = stack.

Any time a problem cares about what came most recently, or matching the nearest unresolved thing, a stack is almost always the answer.

The counterexample test. When you think of an approach, trace it through "([)]" before committing. This string has balanced counts (one of each bracket type), so any approach that only checks counts will incorrectly return true. The string should return false because [ was opened after (, so [ must be closed before (.

"([)]"
 ^ open (   stack: ['(']
  ^ open [  stack: ['(', '[']
   ^ close ) top is '[', not '(' → INVALID

Why two stacks fail. Collecting all openers in one stack and all closers in another checks multiset equality, not order. Comparing them at the end tells you the types match somewhere in the string, but not that they nest correctly. Deferring the match loses order information.

The single-stack insight. Match immediately when you see a closer. The top of the stack must be its matching opener right now. If it is not, fail. No deferred comparison needed.

Mental model: pending business. Think of the stack as a list of unresolved promises:

See (   →  push: "I owe a )"
See [   →  push: "I owe a ]"
See )   →  top must be (. If yes, resolve (pop). If no, fail.
End     →  any pending items? Fail (unclosed openers).

The broader pattern. Single stack whenever you need to match the current item with the nearest unresolved past item:

Problem	”Unresolved” item on the stack
Valid Parentheses	unmatched opener
Largest Rectangle in Histogram	bar that hasn’t found a shorter right boundary
Daily Temperatures	day that hasn’t found a warmer future day
Decode String `"3[a2[c]]"`	(count, partial string) waiting for its `]`
Asteroid Collision	asteroid still alive, waiting for a collision or clear path

Summary

Approach	Time	Space
Repeated replacement	$O(n²)$	$O(n)$
Stack + if/elif	$O(n)$	$O(n)$
Stack + pair-map	$O(n)$	$O(n)$

All stack approaches have the same asymptotic complexity; the pair-map version is the cleanest to write and generalizes to larger character sets.

# Quick smoke tests, paste into a REPL or save as test_valid_parentheses.py and run.
# Uses the canonical implementation (Approach 3: stack + pair-map).

def is_valid(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

def _run_tests():
    assert is_valid("()") == True
    assert is_valid("()[]{}") == True
    assert is_valid("(]") == False
    assert is_valid("([)]") == False
    assert is_valid("{[]}") == True
    assert is_valid("") == True
    assert is_valid("(") == False
    assert is_valid(")") == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function isValid(s: string): boolean {
    const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
    const stack: string[] = [];
    for (const ch of s) {
        if (Object.values(pairs).includes(ch)) {
            stack.push(ch);
        } else {
            if (!stack.length || stack.pop() !== pairs[ch]) return false;
        }
    }
    return stack.length === 0;
}

console.assert(isValid('()') === true);
console.assert(isValid('()[]{}') === true);
console.assert(isValid('(]') === false);
console.assert(isValid('([)]') === false);
console.assert(isValid('{[]}') === true);
console.assert(isValid('') === true);
console.assert(isValid('(') === false);
console.assert(isValid(')') === false);
console.log('all tests pass');

Stacks, LIFO matching of open/close delimiters
Strings, input
Hash Tables, pair-map for close→open lookup

Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

20. Valid Parentheses (Easy)

Problem

Try it yourself

Approach 1: Brute force, repeated replacement

Approach 2: Stack with if/elif chain

Approach 3: Stack with a pair-map (cleanest)

How to recognize this pattern

Summary

Test cases

Related data structures

Related concepts