Beyond Big O

Balanced delimiters

Balanced delimiters

Easy

Solution guide

Reveal solution guide — spoilers

Approach

  1. Keep a stack of unmatched opening delimiters, or equivalently the closing delimiters they require.
  2. Push for each opening parenthesis, bracket or brace. For a closing delimiter, reject immediately if the stack is empty or its top requires a different closing kind; otherwise pop.
  3. Accept only if the stack is empty after scanning every character. Other character handling is unnecessary because inputs contain only the six supported delimiters.

Why it works

The stack stores open groups in nesting order, with the most recently opened group on top. A closing delimiter must close that group before any enclosing group. Matching and popping enforces both kind and order; a remaining opening delimiter at EOF proves an unclosed group.

Complexity

O(n) time and O(n) worst-case auxiliary space for n delimiter characters. Each opening is pushed once and popped at most once.

Edge cases to check

  • Empty text is balanced, and adjacent complete groups are allowed.
  • The crossed sequence "([)]" is invalid even though counts of each kind match.
  • An early closing delimiter fails immediately; leftover openings fail at the end.
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…