Valid Brackets (and the Minimum Fix)

Pattern: Hashing, Stacks and Bit Tricks (Must-Know Classics) · Difficulty: Easy · Asked at: Amazon, Meta, Google, Bloomberg

Classic version: LeetCode 20 · LeetCode 921

Problem

1. is_valid(s): s contains only ()[]{}. Return True if every bracket is closed by the same type in the correct order.
2. min_insertions(s): s contains only ( and ). Return the minimum number of brackets to insert to make it balanced.

Examples

is_valid("()[]{}")  → True
is_valid("(]")      → False
is_valid("([)]")    → False
is_valid("{[]}")    → True
min_insertions("())")   → 1
min_insertions("(((")   → 3

Starter code

def is_valid(s: str) -> bool:
    pass


def min_insertions(s: str) -> int:
    pass

Hints

Where this shows up in data engineering

Stack-based matching is the core of parsing: validating nested JSON before loading, checking SQL/template balance in generated code, and walking nested structures (flattening JSON, building trees from parent/child events). The counter variant shows you know when a full stack is unnecessary.

Solution

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


def min_insertions(s: str) -> int:
    open_count = inserts = 0
    for ch in s:
        if ch == "(":
            open_count += 1
        elif open_count:
            open_count -= 1
        else:
            inserts += 1                 # unmatched ')': insert a '(' before it
    return inserts + open_count          # close every remaining '('

Tests

Your solution should pass these:

assert is_valid("()") is True
assert is_valid("()[]{}") is True
assert is_valid("(]") is False
assert is_valid("([)]") is False
assert is_valid("{[]}") is True
assert is_valid("(") is False
assert is_valid("]") is False
assert is_valid("") is True
assert min_insertions("())") == 1
assert min_insertions("(((") == 3
assert min_insertions("()))((") == 4
assert min_insertions("") == 0

Explanation

Validity: the stack holds unmatched openers; each closer must match the most recent one (last opened, first closed). Both an empty-stack closer and leftover openers are failures. O(n) time, O(n) space.

Minimum insertions: with one bracket type, the stack only ever holds (, so a counter suffices. An unmatched ) forces an insertion immediately; unmatched ( at the end each need a ). O(n) time, O(1) space.

Pitfall: checking only counts (s.count("(") == s.count(")")) accepts ")(".

Follow-up questions