Valid Parentheses: Check That Every Bracket Closes in the Right Order

Problem

You get a string made only of the characters ( ) [ ] { }. It is valid when every opening bracket is closed by the same type of bracket, closings happen in the reverse order of openings (inner pairs close first), and no closing bracket appears without an opener. Return True if the string is valid. This is widely known as LeetCode 20, Valid Parentheses.

Examples

"{[()]}"   ->  True
"([)]"     ->  False   (crossed: ] closes while ( is still open)
"(("       ->  False   (never closed)
""         ->  True

Approach 1: brute force

Repeatedly delete adjacent matching pairs (), [] and {} until nothing changes; the string is valid if it becomes empty.

def is_valid_brute(s):
    prev = None
    while prev != s:
        prev = s
        s = s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

Complexity: O(n²) time (up to n/2 rounds, each O(n)), O(n) space for the new strings.

Approach 2: optimal

Key insight: the most recently opened bracket must be the first one closed. “Last in, first out” is exactly a stack.

Walkthrough on "{[()]}":

Char	Action	Stack after
{	push	{
[	push	{ [
(	push	{ [ (
)	top is (: pop	{ [
]	top is [: pop	{
}	top is {: pop	empty → True

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

Complexity: O(n) time, O(n) space in the worst case (all openers).

Tests

import random

for f in (is_valid, is_valid_brute):
    assert f("{[()]}") is True
    assert f("([)]") is False                # crossed
    assert f("((") is False                  # unclosed
    assert f("") is True                     # empty
    assert f(")") is False                   # single closer
    assert f("(") is False                   # single opener
    assert f("()[]{}") is True               # sequence
    assert f("]") is False and f("(]") is False   # wrong type

assert is_valid("(" * 50_000 + ")" * 50_000) is True     # deep nesting

random.seed(33)
for _ in range(500):
    s = "".join(random.choice("()[]{}") for _ in range(random.randint(0, 10)))
    assert is_valid(s) == is_valid_brute(s)

Edge cases and pitfalls

• Check that the stack is non-empty before reading its top; a leading closer otherwise raises an IndexError.
• Return not stack at the end, not True: leftover openers mean invalid.
• Counting each bracket type separately is wrong: "([)]" has balanced counts but is invalid.
• An odd-length string can be rejected immediately as a quick optimisation.

Where this shows up in data engineering

Every parser for nested formats uses this. Validating that a JSON payload’s braces and brackets are balanced, or that SQL generated by a templating tool has matching parentheses, is a stack check. Streaming JSON parsers keep exactly such a stack to know which object or array they are inside.