Balacing brackets

Balancing brackets = checking whether every opening bracket has a matching closing bracket in the correct order.

Types usually considered:

• ()
• []
• {}

---

Core idea (stack method)

Use a stack:

1. Read characters left → right.
2. If opening bracket → push onto stack.
3. If closing bracket →
   • stack empty → invalid
   • top doesn’t match → invalid
   • else pop.
4. End → stack must be empty.

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

---

Example

Input:

{[()]}

Process:

{   push
[   push
(   push
)   pop
]   pop
}   pop

Stack empty → balanced.

---

Python (clean version)

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

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

    return len(stack) == 0

---

Edge cases people miss

• "(]" → order mismatch
• "(((" → leftover opens
• "))" → early close
• "" → balanced
• "a+(b*c)" → ignore non-brackets

---

Interview twist

If asked minimum removals to balance → count unmatched opens + closes while scanning once.

If asked longest valid parentheses → stack indexes or DP.

---

Further reading:

• Knuth — The Art of Computer Programming, Vol. 1 (stack parsing)
• Aho, Sethi, Ullman — Compilers: Principles, Techniques & Tools