Balanced Brackets

Editorial

Balanced Brackets is a classic stack interview problem: verify that every opening bracket is closed by the correct type in the right order across (), [], and {}.

Approach

Push each opening bracket onto a stack. On a closing bracket the top of the stack must be its matching opener — pop and compare; if it doesn't match, or the stack is empty, the string is unbalanced. A valid string ends with an empty stack.

pairs = {')':'(', ']':'[', '}':'{'}
stack = []
for c in s:
    if c in '([{': stack.append(c)
    elif not stack or stack.pop() != pairs[c]:
        return False
return not stack

Note

With a single bracket type you could drop the stack and track a running counter, but multiple types need the stack to remember which bracket is open.

Complexity

Time: O(n). Space: O(n).