Coding Interview Patterns Module 8 – Stacks and monotonic stacks
Bracket matching and minimum fixes
Check that brackets of three kinds are balanced in one pass with a stack, then count the fewest insertions or removals that balance a string.
What you will learn
- Check a text with (), [] and {} in one pass with a stack, and say why it takes O(n) time
- Report where a text first breaks, and in which unit each of 14 languages counts that position
- Count the fewest insertions or removals that balance one kind of bracket, and prove the count
- Explain why mixed kinds of bracket need a dynamic program, and test a checker against a brute force
Before you start
What you’ll learn · Before you start
What you will learn
- Check a text with (), [] and {} in one pass with a stack, and say why it takes O(n) time
- Report where a text first breaks, and in which unit each of 14 languages counts that position
- Count the fewest insertions or removals that balance one kind of bracket, and prove the count
- Explain why mixed kinds of bracket need a dynamic program, and test a checker against a brute force
Before you start
On this page
Bracket matching checks that every opening bracket in a text is closed by its own kind, in the right order: {[()]}
is balanced, while ([)] and (() are not. One pass with a stack does it. Push each opener; when a closer arrives,
the opener on top of the stack must be its partner, and it is popped; at the end nothing may be left open. That takes
O(n) time for n characters. Minimum fixes is the question that comes next: the fewest brackets to insert or remove so
that a text becomes balanced. For one kind of bracket, a counter in the same pass answers it. Below are an original
version of both problems, a brute force too slow at their limits, and the one-pass ideas worked through examples.
Deleting matched pairs is right, but slow on deep nesting
The problem
A messaging service fills in templates such as Hi {name}, order [#{id}] ships (in {days} days) before it sends
them. A template may be saved only if its brackets are balanced: every (, [ and { is closed later by its own
kind, ), ] or }, and a bracket opened inside another one is closed before it. Every other character is text.
Return True for a balanced template and False otherwise. A template has at most 1,000,000 characters.
The code in this lesson is checked on these three templates:
Hi {name}, order [#{id}] ships (in {days} days)is balanced.Total: {sum(a[i)]}is not: the)at position 15 tries to close the(while the[opened after it is still open.(see [note 3]is not: the(at position 0 is never closed.
The brute force: delete matched pairs until none is left
Drop the text, then delete every adjacent pair (), [] or {}, and repeat until a round deletes nothing. The
template is balanced exactly when nothing is left. That is easy to trust but slow: on a template nested d brackets
deep, only the innermost pairs are ever adjacent, so each round deletes a pair or two while it reads all the rest of
the text, round after round.
"""The brute force: delete adjacent matched pairs, (), [] and {}, until none is left."""
import time
PAIRS = ("()", "[]", "{}")
def balanced_brute(template):
"""True when every bracket is closed by its own kind, in nested order; also how many characters it read."""
s = "".join(ch for ch in template if ch in "()[]{}") # the text between brackets does not matter
read = 0
while True:
shorter = s
for pair in PAIRS:
read += len(shorter) # each replace() reads the whole string
shorter = shorter.replace(pair, "")
if shorter == s: # no adjacent pair left to delete
return s == "", read
s = shorter
for template in ["Hi {name}, order [#{id}] ships (in {days} days)", "Total: {sum(a[i)]}", "(see [note 3]"]:
print(f"{template!r}: {balanced_brute(template)[0]}")
def nested(depth):
"""depth openers of mixed kinds, then their closers: one pair can go per round."""
openers = "([{" * (depth // 3 + 1)
closers = {"(": ")", "[": "]", "{": "}"}
head = openers[:depth]
return head + "".join(closers[ch] for ch in reversed(head))
per_char = 0.0
for depth in (5_000, 10_000, 20_000):
template = nested(depth)
best = float("inf")
for _ in range(3): # the fastest of three runs: the least disturbed by other programs
start = time.perf_counter()
ok, read = balanced_brute(template)
best = min(best, time.perf_counter() - start)
assert ok
per_char = best / read
print(f"depth {depth:,} ({len(template):,} characters): {read:,} characters read in {best * 1000:,.0f} ms")
# At the limit, nested 500,000 deep: 25 times the depth of the last run, so about 625 times the characters.
read *= (500_000 // 20_000) ** 2
print(f"depth 500,000 (1,000,000 characters): about {read / 1e9:,.0f} billion characters, {read * per_char / 60:,.0f} minutes at that speed")Output
'Hi {name}, order [#{id}] ships (in {days} days)': True
'Total: {sum(a[i)]}': False
'(see [note 3]': False
depth 5,000 (10,000 characters): 50,010,000 characters read in 33 ms
depth 10,000 (20,000 characters): 200,000,000 characters read in 564 ms
depth 20,000 (40,000 characters): 800,040,000 characters read in 1,439 ms
depth 500,000 (1,000,000 characters): about 500 billion characters, 15 minutes at that speed
This output changes from run to run: the times depend on the computer and on what else it is doing
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute_force.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each doubling of the depth reads four times as many characters, as an O(n²) method should; the times follow, unevenly, because other programs disturb them. At the limit of a million characters, nested half a million deep, that is about 500 billion characters, many minutes of work where the time limit allows about a second.
What to notice
Look at what each round deletes: a closer and the nearest opener before it that is still there. So a closer always belongs to the most recent opener that is still open, which is the stack cue of the module overview.
Checkpoint
Check: Deleting matched pairs, and what it costs
One pass with a stack finds the first problem
Read the template once, from left to right, and keep the open brackets on a stack:
- Skip text characters, and push every opener.
- At a closer, look at the top. If nothing is open, or the top is not its partner, the template is not balanced, and this closer is its first problem. Otherwise pop the top.
- At the end, the template is balanced only if the stack is empty. If it is not, the opener at the bottom is the earliest one that was never closed.
Each character costs at most one push or one pop, so the check takes O(n) time, and O(n) memory when every bracket is open at once. The diagram follows the second example to its first problem.
A closer must match the newest open bracket
Text description of the diagram
The diagram shows the stack of open brackets after each bracket of the template Total: {sum(a[i)]}, from top to bottom. The text between the brackets changes nothing and is not drawn. The newest open bracket, the top of the stack, has a thick border.
- At the start nothing is open, and the stack is empty.
- The { at position 7 is pushed: the stack holds { from position 7.
- The ( at position 11 is pushed: the stack holds { and (, with ( on top.
- The [ at position 13 is pushed: the stack holds {, ( and [, with [ on top.
- The ) at position 15 is compared with the top. The top is [, and the partner of ) is (, so they do not match.
The check stops at position 15: the closing ) tries to close the ( while the [ opened after it is still open, so the brackets cross. That position is the first problem in the template.
Step through the same template, or type one of your own:
- being compared or looked at
- being moved or written
Pseudo-code
-
for each character c: -
if c opens a bracket: push c -
if c closes a bracket: -
if the stack is empty or its top does not match c: return "not balanced" -
pop -
return the stack is empty ? "balanced" : "not balanced"
Check whether the brackets in "Total: {sum(a[i)]}" are balanced. Each opening bracket waits on a stack; each closing one must match the most recent opening one still waiting.
When it finishes: Not balanced.
Try your own input
The third example ends with a bracket still open:
| Bracket | Step | Still open |
|---|---|---|
( at 0 |
push | ( at 0 |
[ at 5 |
push | ( at 0, [ at 5 |
] at 12 |
the top is [: pop |
( at 0 |
| the end | the stack is not empty | the problem is at 0 |
Checkpoint
Check: One pass with a stack of open brackets
For one kind of bracket, a counter gives the fewest fixes
A formula with only round brackets raises the second question: what are the minimum fixes, the fewest brackets to
insert or remove, that balance it? A counter replaces the stack, because every open bracket is the same. Read from
the left and count the ( still open. A ) closes one of them; a ) that arrives when the count is 0 has no
partner and needs one fix. At the end, every ( still open needs one fix too. So the minimum is the closers without
a partner plus the openers never closed, for insertions and removals alike.
In ())((, the ) at position 2 has no partner and two ( stay open, so three fixes are needed: insert brackets to
get ()()(()), or remove positions 2, 3 and 4 to keep (). Step through the count:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- Start. Nothing has been read, so nothing is open and no closer is waiting for a partner.
- ( at 0. An opener raises the open count to 1.
- ) at 1. A closer with something open closes one opener, so the open count falls back to 0.
- ) at 2. This closer finds nothing open: it has no partner, so it needs one fix. The count of such closers becomes 1.
- ( at 3. An opener raises the open count to 1.
- ( at 4. Another opener raises the open count to 2.
- The end. Each of the 2 brackets still open needs a closer, and the 1 lonely closer needs an opener: 1 + 2 = 3 fixes, inserted or removed.
Mixed kinds need more than a counter. Two natural greedy rules, closing the top early or skipping a closer that does not match, each give wrong counts, and a A method that solves a problem from the answers to its smaller pieces, each worked out once and stored. Here the pieces are the stretches of the string, and the answer is the fewest fixes of each. over the pieces of the string gives the right count in O(n³).
Checkpoint
Check: The fewest fixes for one kind of bracket
Practise: count the fewest fixes
Exercise · Easy · Python
Count the fewest brackets that balance a formula
A formula editor accepts only round brackets. Write min_fixes(s), which returns the fewest brackets that must be inserted into s to make every ( closed by a later ) and every ) close an earlier (.
sholds only the characters(and), and it may be empty. It has at most 1,000,000 characters.- Inserting a bracket may happen anywhere: before the first character, between two characters or after the last.
- Return a number, not the fixed string.
min_fixes("())((") # 3: one ")" has no partner, and two "(" are never closed
min_fixes("(()") # 1
min_fixes(")(") # 2Work one more example by hand before you code: a string that starts with three closers.
Starter code · fixes.py
def min_fixes(s):
"""The fewest brackets to insert so that every bracket of s has a partner."""
# Replace this line with your code.
return 0The sample tests · test_fixes.py
import random
import sys
from fixes import min_fixes
LINE_LIMIT = 4_000_000
def trusted(s):
"""A slow reference the tests trust: delete "()" pairs until none is left; every bracket left needs one fix."""
while "()" in s:
s = s.replace("()", "")
return len(s)
class TooSlow(Exception):
pass
def run_limited(s):
"""Call min_fixes, stopped after LINE_LIMIT executed lines (a fair time limit)."""
executed = 0
def count_lines(frame, event, arg):
nonlocal executed
if event == "line":
executed += 1
if executed > LINE_LIMIT:
raise TooSlow
return count_lines
sys.settrace(count_lines)
try:
return min_fixes(s)
except TooSlow:
raise AssertionError(f"too slow: more than {LINE_LIMIT:,} lines ran; aim for one pass") from None
finally:
sys.settrace(None)
def test_examples():
"""the examples from the prompt"""
assert min_fixes("())((") == 3
assert min_fixes("(()") == 1
assert min_fixes(")(") == 2
def test_nothing_to_fix():
"""an empty formula and balanced ones"""
assert min_fixes("") == 0
assert min_fixes("()") == 0
assert min_fixes("(())()") == 0
def test_only_one_kind_of_bracket():
"""only openers, or only closers"""
assert min_fixes("(((") == 3
assert min_fixes(")))") == 3
def test_closers_first():
"""closers that come before any opener"""
assert min_fixes("))((") == 4
assert min_fixes("))()") == 2
def test_random_formulas():
"""200 random formulas against the slow reference"""
rng = random.Random(7)
for _ in range(200):
s = "".join(rng.choice("()") for _ in range(rng.randrange(12)))
assert min_fixes(s) == trusted(s), s
def test_long_formula():
"""a formula of 200,000 brackets, checked against a line limit"""
s = ")" * 1_000 + "()" * 99_000 + "(" * 1_000
assert run_limited(s) == 2_000A hint
Read the string once, from left to right, and keep one number: how many ( are still open. What should happen to that number at a ), and what does a ) mean when the number is already 0? Whatever is still open at the end needs fixing too.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
These questions start with the idea you know least.
Practice that adapts to you
Practise this lesson
9 questions about 10 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.
The one-pass check in 14 languages, with its proof Pro: opens with a Pro, Premium or Ultimate pass
The check takes a dozen lines in every language, and each language counts positions in its own unit. Here it is in 14 languages with their recorded runs, the invariant that proves the stack right, and a stress test that catches two plausible slips.
In this part:
- The check in 14 languages, each counting positions its own way
- Why a closer may close only the top: the invariant and its proof
- Two slips, caught by a stress test
2 runnable examples (Python) · about 12 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Fewest insertions and removals: proved, rebuilt and checked Pro: opens with a Pro, Premium or Ultimate pass
The counter gives a number. This part proves that no smaller fix exists, rebuilds the fixed text both ways, and shows why two or more kinds of bracket need a dynamic program instead of a greedy rule.
In this part:
- Why the counter’s count is the minimum: a proof with prefix balances
- Two or more kinds: two greedy rules fail, reproduced, and a dynamic program
2 runnable examples (Python) · about 5 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Edge cases, variants and follow-ups, with measured numbers Pro: opens with a Pro, Premium or Ultimate pass
A check that is right can still be slow, fail on deep input or hold more memory than it needs. This part measures the one pass at its limit, compares the four methods, and answers the variants and follow-up questions that interviews add.
In this part:
- Measured: a million characters, the stack’s memory and the recursion limit
- Checking and fixing side by side: two trade-off tables
- Edge cases and common bugs
- Variants, with answers
- Follow-up questions, answered
1 runnable example (Python) · about 7 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Interview questions
-
Fresher to mid · Warm-up
When is a counter enough to check brackets, and when do you need a stack?
A counter is enough when there is only one kind of bracket. Count the openers still open: an opener adds one, a closer takes one away, the count must never drop below zero, and it must end at zero. With two or more kinds, counting each kind on its own is not enough, because it ignores order: ([)] has one opener and one closer of each kind, and no count ever drops below zero, yet the brackets cross. A closer must match the most recent opener that is still open, and only a stack remembers which one that is. The memory differs too: a counter needs O(1), while a stack holds every bracket that is open at once, O(n) in the worst case.
-
Mid to senior
A code editor must underline the first bracket that breaks a file of up to 20 MB, and update the underline within 16 ms of every keystroke. A full rescan is too slow. What do you store, and what does one edit cost?
-
Mid to senior
A candidate counts the fewest insertions that balance a string of (), [] and {} with a stack: when a closer does not match the top, insert the top's closer. Give an input where this is wrong, a correct method, and its cost for a string of 500 characters.
-
Fresher to mid
A spreadsheet formula uses only round brackets. Remove the fewest brackets so that it becomes valid, and return the result. Explain why no smaller fix exists, and how your answer changes when the formula has 10⁷ characters and memory is tight.
Two changes an interviewer might make to the problem:
Checkpoint
Interview round: two follow-up questions
Key takeaways
- Bracket matching is one pass with a stack of open brackets: a closer must match the top, and nothing may be left open at the end.
- The brute force, deleting adjacent pairs round after round, is O(n²) on deep nesting: minutes at a million characters.
- For one kind of bracket, the minimum fixes are the closers without a partner plus the openers never closed, and a counter finds them in the same pass.
References
- The Python Tutorial: Using Lists as Stacks (Python Software Foundation)
- string: Format String Syntax (Python Software Foundation)
- sys.getrecursionlimit() (Python Software Foundation)
- tracemalloc: trace memory allocations (Python Software Foundation)
- String: length (MDN Web Docs (Mozilla))
- Java SE 25 API: ArrayDeque (Oracle)
- Java SE 25 API: String (charAt and UTF-16) (Oracle)
- std::vector::back (cppreference.com)
- The Go Programming Language Specification: String types (The Go Authors)
- RFC 3629: UTF-8, a transformation format of ISO 10646 (IETF)
- AddressSanitizer (The Clang Team (LLVM Project))
- Strings and characters (C# programming guide): UTF-16 code units (Microsoft)
- str::char_indices (Rust standard library): byte positions of each char (The Rust Project)
- The Swift Programming Language: strings and characters (extended grapheme clusters) (Swift.org)
- Strings (Kotlin documentation) (JetBrains)
- String class (Dart core library): UTF-16 code units (Dart (Google))
- Strings (PHP manual): a string is a series of bytes (The PHP Group)
- Class String (Ruby 4.0 documentation): each_char (Ruby)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress