Coding Puzzle: Bracket Balance

• Difficulty: Medium
• Patterns:
  • Stack

Problem Definition

Given a string of bracket characters ({[]}), determine if the brackets in the string are balanced.

Examples

Some test cases to verify our solution.

assert bal("({[]})")
assert bal("{}[]()")
assert not bal("{(})")
assert not bal("{[[)))")
assert not bal("(")
assert not bal(")")
assert bal("({}{}[{}]())")

Solution

We'll use a stack to track the closing brackets for all open brackets we encounter. If at any point we close a bracket that is not at the top of the stack, we return False. Whenever we close a bracket, we'll pop the closing character off the stack. If at the end there are elements in the stack, then we'll return False.

# Bracket map
M = {
    "(": ")",
    "{": "}",
    "[": "]",
}

def bal(s):
    if len(s) == 0:
        return True
    stack = []
    for c in s:
        if c in M:
            stack.append(M[c])
        elif len(stack) == 0:
            return False
        elif stack[-1] == c:
            stack.pop()
        else:
            return False
    return len(stack) == 0

Complexity

Let $n = $ len(s).

Since we are traversing each element in s at most once, the runtime complexity should be $O(n)$.

Since the stack might at worst contain $n$ elements, auxiliary space complexity should be $O(n)$.