Tag nest

The string s contains only the brackets (), [] and {}. Return whether it is balanced: every opening bracket must have a matching closing bracket of the same type, and pairs must be correctly nested. A closing bracket cannot appear without its opening bracket. The empty string is balanced.

Example:

is_balanced("([])")  →  True

The pair [] is fully enclosed by (). Both pairs match and are correctly nested.

is_balanced("([)]")  →  False

In ([)], ) closes the outer pair before ] closes the inner pair, so the nesting is invalid.

Pattern: stack — push openers; a closer must match the top

Need a hint?

Reveal one step at a time. Stop when you have enough to keep going.

1 · What to notice

The next closing bracket must match the most recent opening bracket that has not been closed. Which structure remembers items in that order?

2 · Walk through an example

For ([]), push ( and then [. At ], the stack top is [, so remove it. At ), remove (. The stack ends empty. For ([)], the top is [ when ) arrives: the types differ, so reject immediately. Counting brackets alone cannot detect incorrect nesting.

3 · Pseudocode and self-check

Language-independent pseudocode. Indices start at 0; ← means assignment. Ranges with an upper bound exclude that bound.

stack ← []
matching ← {')': '(', ']': '[', '}': '{'}
FOR EACH bracket IN s:
    IF bracket IN ['(', '[', '{']:
        PUSH bracket ONTO stack
    ELSE:
        IF stack IS EMPTY OR TOP(stack) ≠ matching[bracket]:
            RETURN false
        POP stack
RETURN stack IS EMPTY

Check your reasoning

Empty string → true. A lone closing bracket → false. Unclosed opening brackets also mean false. Time O(n), auxiliary space O(n).

Python TypeScript Go Rust Pro Java Pro Swift Pro

Tag nest

Cookies and analytics