Loading page…
Practice problem · easy
An engineering platform lets teams write deployment settings in a small config language. Settings nest inside three kinds of brackets: round (), square [] and curly {}.
Before a config is deployed, a linter checks the brackets on their own. Every opening bracket must be closed by a bracket of the same kind. Brackets must also close in the right order: the one opened last closes first. A config can hold up to 100,000 brackets, and the linter runs on every save.
Write is_balanced(config).
config is a string made only of the six characters (, ), [, ], { and }.true when every bracket is closed by the same kind, in the right order. Return false otherwise.Input: config = "([]{})"
Output: true| Step | Character | What happens | Stack after (bottom to top) |
|---|---|---|---|
| 1 | ( |
an opener: push it | ( |
| 2 | [ |
an opener: push it | ( [ |
| 3 | ] |
a closer: the top is [, a match, pop |
( |
| 4 | { |
an opener: push it | ( { |
| 5 | } |
a closer: the top is {, a match, pop |
( |
| 6 | ) |
a closer: the top is (, a match, pop |
empty |
The stack is empty at the end, so every bracket was closed.
Input: config = "(]"
Output: falseThe ] arrives while the top of the stack is (. The kinds differ, so the config is broken.
Input: config = ")("
Output: falseThe ) arrives first, when no bracket is open. There is nothing to match it with.
1 ≤ length of config ≤ 10^5config contains only (, ), [, ], { and }One pass over 10^5 characters is cheap. A plan that rescans the whole text once for every level of nesting is about n^2 / 2 steps: 5 × 10^9 for a config that is 50,000 levels deep. That is too slow.
So read each character once. The rule "the bracket opened last closes first" says what to remember between characters: the openers that are still waiting, newest last.
is_balanced · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.