061. Balanced Brackets

Foundation · Download this solution · All solutions and shared helpers

Problem

Decide whether a string containing only (), [] and {} is correctly nested and matched. Empty input is balanced. Every closing bracket must match the most recent unmatched opening bracket; having equal total counts is not sufficient.

Examples

Example 1

balanced_brackets("([{}])")
=> True

Each closing bracket matches the innermost opening.

Example 2

balanced_brackets("([)]")
=> False

Counts match but nesting crosses.

Example 3

balanced_brackets("")
=> True

There are no unmatched brackets.

Reveal the worked solution and reasoning

Why this mechanism works

Nested structure is last-opened, first-closed. Store unresolved opening brackets on a stack. A closing bracket has only one legal partner: the top. At the end, unmatched openings are as invalid as unmatched closings.

State and boundaries

stack contains opening brackets whose closing partners have not yet appeared, in nesting order.

Protocol

Push every opening bracket.
For a closing bracket require a nonempty stack with the matching top.
Pop that match.
Accept only if the stack is empty at the end.

Visualization

([{}])
open stack: ( -> ([ -> ([{
close order: } -> ] -> )

Python implementation

def balanced_brackets(text):
    matching = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in text:
        if char in '([{':
            stack.append(char)
        else:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
    return not stack

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

balanced_brackets("([{}])")

L2 balanced_brackets: matching = {')': '(', ']': '[', '}': '{'}
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}

L3 balanced_brackets: stack = []
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=[]

L4 balanced_brackets: for char in text:
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=[]; char='('

L6 balanced_brackets: stack.append(char)
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char='('

L4 balanced_brackets: for char in text:
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char='['

L6 balanced_brackets: stack.append(char)
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[']; char='['

L4 balanced_brackets: for char in text:
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[']; char='{'

L6 balanced_brackets: stack.append(char)
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[', '{']; char='{'

... 2 intermediate state changes omitted ...

L4 balanced_brackets: for char in text:
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[']; char=']'

L10 balanced_brackets: stack.pop()
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char=']'

L4 balanced_brackets: for char in text:
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char=')'

L10 balanced_brackets: stack.pop()
text='([{}])'; matching={')':'(', ']':'[', '}':'{'}; stack=[]; char=')'

Result: True. Each closing bracket matches the innermost opening.

balanced_brackets("([)]")

L2 balanced_brackets: matching = {')': '(', ']': '[', '}': '{'}
text='([)]'; matching={')':'(', ']':'[', '}':'{'}

L3 balanced_brackets: stack = []
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=[]

L4 balanced_brackets: for char in text:
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=[]; char='('

L6 balanced_brackets: stack.append(char)
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char='('

L4 balanced_brackets: for char in text:
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=['(']; char='['

L6 balanced_brackets: stack.append(char)
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[']; char='['

L4 balanced_brackets: for char in text:
text='([)]'; matching={')':'(', ']':'[', '}':'{'}; stack=['(', '[']; char=')'

Result: False. Counts match but nesting crosses.

Why the solution is correct

Pushing records a newly opened inner context. Matching only the top enforces nesting as well as type. Rejecting an impossible close is necessary, and an empty final stack means every recorded opening was matched exactly once.

Time and space

O(n) time and O(d) stack space, where d is maximum nesting depth.

Common mistakes

Counting bracket types accepts crossing pairs such as ([)]. Forgetting the final emptiness check accepts unfinished openings.

Reasoning card

State: stack contains opening brackets whose closing partners have not yet appeared, in nesting order.

Invariant: Stack contains exactly unresolved opening brackets.

Decision to rehearse: Reject empty-stack closes; compare only with the most recent opener.

Finish: Accept only if the stack is empty at the end

Transfer exercise

Return the index of the first impossible closing bracket, distinguishing it from unmatched openings discovered only at the end.