Balanced Brackets

Tags

Balanced Brackets

Category

Stacks

Difficulty

Medium

Problem Statement

Given a string containing brackets (parentheses (), square brackets [], and curly braces {}), determine whether the brackets are balanced. A string has balanced brackets if every opening bracket has a corresponding closing bracket of the same type, and the brackets are correctly nested.

Intuition

Brackets follow a last-in-first-out (LIFO) pattern: the most recently opened bracket must be the first one closed. This is exactly the behavior of a stack. By pushing opening brackets onto a stack and popping when we encounter closing brackets, we can verify that each closing bracket matches the most recent unmatched opening bracket.

Approach

  1. Initialize an empty stack.
  2. Define a mapping from closing brackets to their corresponding opening brackets.
  3. Iterate through each character in the string:
    • If the character is an opening bracket ((, [, {), push it onto the stack.
    • If the character is a closing bracket (), ], }):
      • If the stack is empty, return false (no matching opening bracket).
      • Pop the top of the stack. If it does not match the expected opening bracket, return false.
    • Ignore non-bracket characters.
  4. After processing all characters, return true if the stack is empty, false otherwise.

Pseudocode

function balancedBrackets(string):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    openers = set('(', '[', '{')

    for char in string:
        if char in openers:
            stack.push(char)
        else if char in matching:
            if stack is empty:
                return false
            if stack.pop() != matching[char]:
                return false

    return stack is empty

Time & Space Complexity

  • Time: O(n) where n is the length of the string. Each character is processed once, and each stack operation is O(1).
  • Space: O(n) in the worst case, where all characters are opening brackets.

Key Insights

  • The stack naturally enforces the correct nesting order.
  • Both conditions must be checked: (1) every closing bracket matches the most recent opening bracket, and (2) no opening brackets remain unmatched at the end.
  • Non-bracket characters are simply ignored.
  • A common mistake is forgetting to check if the stack is empty before popping when a closing bracket is encountered.

Edge Cases

  • Empty string: balanced (vacuously true), return true.
  • String with no brackets: return true.
  • String with only opening brackets: return false (stack is not empty at the end).
  • String with only closing brackets: return false (stack underflow on first closing bracket).
  • Single bracket: return false.
  • Correctly nested but different types interleaved (e.g., "([{}])"): return true.
  • Incorrect nesting (e.g., "([)]"): return false.

Linked mentions