How do you solve Balanced Brackets using the Stack — One Pass (Optimal) approach?

When to use it: The answer they want. Phrase it as 'the most recent opener must match this closer' — LIFO — not just 'use a stack'. Walk the string once. Push every opening bracket. When you hit a closing bracket, the only valid partner is the bracket on top of the stack — pop it and check the types match. After the scan, the stack must be empty. **The LIFO insight that picks the structure.** In `"{[()]}"`, when `)` arrives the open bracket that *must* close is `(` — the one opened most recently. Not `{`, not `[`. 'Most recently opened, not yet closed' is the literal definition of a stack's top. That single observation is why a stack, and nothing simpler, fits: brackets nest, and nesting is last-in-first-out. **Why three separate failure checks, not one.** A balanced string can break in three distinct ways, and a correct solution catches all three: - **Stray closer:** `"]"` or `")("`. A closer arrives but the stack is empty — there is no opener to match. If you blindly `pop()` here, Java throws and Python errors. Check `empty` *before* popping. - **Wrong pair:** `"(]"`. The stack top is `(` but the closer is `]`. Pop, compare types, fail on mismatch. - **Leftover openers:** `"((("`. No mismatch ever happens, but the loop ends with three `(` still on the stack. The final `stack.isEmpty()` check is the only thing that catches this — forgetting it is the single most common bug on this problem. **Why map closers to openers.** Instead of a tangle of `if (c == ')' && top == '(') ...`, build a tiny map `) → (`, `] → [`, `} → {`. On a closer, look up its required opener and compare against the popped value in one line. Cleaner, and it generalises if more pair types appear. **The O(1) early reject.** A balanced string has even length — every bracket is half of a pair. If `s.length()` is odd you can return `false` before scanning a single character. Small, but it signals you think about invariants. Time complexity: O(n). Space complexity: O(n).

Loading…

easyStack QueueAsked very often

Balanced Brackets

Q: How do you solve Balanced Brackets using the Brute Force — Repeated Pair Deletion approach?

When to use it: Mention it to show you understand the structure, then immediately note it is O(n²) and reach for the stack. The defining property of a balanced bracket string is that it is built entirely from innermost empty pairs. `"{[()]}"` contains `"()"`; delete it and you get `"{[]}"`, which contains `"[]"`; delete that and you get `"{}"`; delete that and you get `""`. Reaching the empty string means balanced. **Why repeated deletion works.** Every matched pair, by definition, surrounds a (possibly empty) balanced substring. The *innermost* pairs have nothing between them, so they appear literally as `"()"`, `"[]"`, or `"{}"`. Removing them exposes the next layer out, and the process repeats. If the string is balanced, every character eventually disappears. **Why a single pass is not enough.** One sweep removes only the pairs that are *currently* adjacent. After removal, brand-new adjacencies form — the `"[]"` in `"{[]}"` only became adjacent after `"()"` was gone. So you must loop until a full pass changes nothing. **Why we don't ship this.** Each pass is O(n), and a deeply nested string like `"((((....))))"` peels one layer per pass, giving O(n) passes and O(n²) total. For n = 10⁵ that's 10¹⁰ operations — far too slow. It's a great way to *explain* what balanced means, but the stack does the same job in one pass. Time complexity: O(n²). Space complexity: O(n).

Stack & Queue · 8 of 17 · 8 min

A bracket is any one of (, ), {, }, [, or ]. Two brackets are a matched pair when an opening bracket occurs to the left of a closing bracket of the exact same type.

Given a string s containing only these six characters, determine whether the sequence is balanced: every opening bracket has a corresponding closing bracket of the same type, and pairs are properly nested (the most recently opened bracket is the first one closed).

Return true if balanced, false otherwise.

In plain English

Each closing bracket must cancel the bracket opened most recently — that's last-in-first-out, which is exactly a stack. The string is balanced only if every closer cancels the correct opener AND nothing is left open at the end.

Examples

Example 1

Input: s = "{[()]}"
Output: true
Note: Perfectly nested: ( ) closes, then [ ] closes, then { } closes — stack drains cleanly.

Example 2

Input: s = "([)]"
Output: false
Note: The ')' arrives while '[' is on top of the stack. ')' expects '(' but sees '[' → mismatch.

Example 3

Input: s = "((("
Output: false
Note: No mismatch ever occurs, but three openers are left on the stack at the end → unbalanced.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of the characters ()[]{}
An empty inner sequence is fine — '()' is balanced
Return a boolean (some variants ask for the string 'YES'/'NO')

Clarifying questions4First question: Can the string contain characters other than the six brackets?Explore questions

Q1.Can the string contain characters other than the six brackets?
Per the constraints, no. If it could, decide whether to ignore non-brackets or reject — say it out loud.
Q2.Is the empty string balanced?
Conventionally yes (nothing is unmatched), but the constraint here says length ≥ 1, so you won't hit it. Confirm the convention anyway.
Q3.Do different bracket types interleave, like '([)]'?
That is NOT balanced — the ')' tries to close a '[' that is still open. The stack catches this automatically.
Q4.Return a boolean or a 'YES'/'NO' string?
Depends on the platform. The logic is identical; just format the output at the end.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Scan the string once with a stack. Push every opening bracket; on a closing bracket, the stack top must be the exact matching opener — pop it, otherwise the string is unbalanced. At the end the stack must be empty. O(n) time, O(n) space. The naive 'repeatedly delete (), [], {} until nothing changes' works but is O(n²).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise LIFO matching and pick a stack — and whether you remember all three ways the string can be invalid, not just a wrong-pair mismatch.

Where candidates slip

Forgetting to check the stack is empty at the end (so '(((' passes), or popping from an empty stack on a stray closer like ']'.

How to stand out

Mention the O(1) odd-length rejection, map closers to openers instead of a chain of ifs, and name the LIFO insight explicitly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeated Pair Deletion	`O(n²)`	`O(n)`	Mention it to show you understand the structure, then immediately note it is O(n²) and reach for the stack.	Read
2	Stack — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'the most recent opener must match this closer' — LIFO — not just 'use a stack'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewRead char cIs c an opener?YesNo (closer)Explore the full tree

The decision each character triggers

How to read it:Openers always push. Closers branch into three checks — this is the whole algorithm.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeated Pair Deletion

TimeO(n²)SpaceO(n)

Mention it to show you understand the structure, then immediately note it is O(n²) and reach for the stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A balanced string can always be collapsed by repeatedly removing an innermost empty pair like '()', '[]', or '{}'. What's left after removing all of them?

2Hint 2Explore hint

Keep replacing every occurrence of '()', '[]', '{}' with nothing, in a loop, until the string stops changing.

3Hint 3Explore hint

If the final string is empty, it was balanced. If something non-empty remains, it wasn't. Each full pass is O(n) and you may need O(n) passes.

A · Core idea

The defining property of a balanced bracket string is that it is built entirely from innermost empty pairs. "{[()]}" contains "()"; delete it and you get "{[]}", which contains "[]"; delete that and you get "{}"; delete that and you get "". Reaching the empty string means balanced.

Why repeated deletion works. Every matched pair, by definition, surrounds a (possibly empty) balanced substring. The innermost pairs have nothing between them, so they appear literally as "()", "[]", or "{}". Removing them exposes the next layer out, and the process repeats. If the string is balanced, every character eventually disappears.

Why a single pass is not enough. One sweep removes only the pairs that are currently adjacent. After removal, brand-new adjacencies form — the "[]" in "{[]}" only became adjacent after "()" was gone. So you must loop until a full pass changes nothing.

Why we don't ship this. Each pass is O(n), and a deeply nested string like "((((....))))" peels one layer per pass, giving O(n) passes and O(n²) total. For n = 10⁵ that's 10¹⁰ operations — far too slow. It's a great way to explain what balanced means, but the stack does the same job in one pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "{[()]}"

Array state

start

original string

{

[0]

[

[1]

(

[2]

)

[3]

]

[4]

}

[5]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isBalanced(String s) { String prev; do { prev = s; s = s.replace("()", "").replace("[]", "").replace("{}", "");Explore the full code

solution.javaJava

Brute Force — Repeated Pair Deletion — reference

4 teaching notes

1
public boolean isBalanced(String s) {
2
    String prev;
3
    do {
4
        // Remember the string before this pass so we can detect when nothing changes.
5
        prev = s;
6
        // Strip every adjacent empty pair. Each replace is O(n) and builds a new
7
        // string.
8
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
9
    // Keep looping until a full pass removes nothing — that's the fixed point.
10
    } while (!s.equals(prev));
11
    // Empty means every bracket was paired away → balanced.
12
    return s.isEmpty();
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

This approach reveals the recursive structure of balanced strings — they collapse from the inside out. The stack is just a way to do all of that collapsing in a single left-to-right pass instead of repeated rescans.

ComplexityO(n²) time, O(n) space — Each deletion pass scans the whole string (O(n)) and may remove only one layer of pairs, so up to n/2 passes → O(n²) total. The intermediate string copies cost O(n) space.

E · Edge cases and pitfalls3Doing a single replace pass instead of looping — '{[]}' wouldn't fully collapse.Explore edge cases

Pitfalls

Doing a single replace pass instead of looping — '{[]}' wouldn't fully collapse.
Using this on large inputs — O(n²) times out at n = 10⁵.
Forgetting that string replace allocates a new string each time, hiding extra cost.

03.2

Approach 2 of 2 · Optimal

Stack — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'the most recent opener must match this closer' — LIFO — not just 'use a stack'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When you see a closing bracket, which opening bracket must it match? The one opened most recently and not yet closed. What structure gives you 'most recent, not yet handled' in O(1)?

2Hint 2Explore hint

Push every opener onto a stack. On a closer, the correct partner is whatever is on top — pop it and verify it's the right type.

3Hint 3Explore hint

Three ways to fail: the stack is empty when a closer arrives (no partner), the popped opener is the wrong type (mismatch), or the stack is non-empty at the end (unclosed openers).

A · Core idea

Walk the string once. Push every opening bracket. When you hit a closing bracket, the only valid partner is the bracket on top of the stack — pop it and check the types match. After the scan, the stack must be empty.

The LIFO insight that picks the structure. In "{[()]}", when ) arrives the open bracket that must close is ( — the one opened most recently. Not {, not [. 'Most recently opened, not yet closed' is the literal definition of a stack's top. That single observation is why a stack, and nothing simpler, fits: brackets nest, and nesting is last-in-first-out.

Why three separate failure checks, not one. A balanced string can break in three distinct ways, and a correct solution catches all three:

Stray closer: "]" or ")(". A closer arrives but the stack is empty — there is no opener to match. If you blindly pop() here, Java throws and Python errors. Check empty before popping.
Wrong pair: "(]". The stack top is ( but the closer is ]. Pop, compare types, fail on mismatch.
Leftover openers: "(((". No mismatch ever happens, but the loop ends with three ( still on the stack. The final stack.isEmpty() check is the only thing that catches this — forgetting it is the single most common bug on this problem.

Why map closers to openers. Instead of a tangle of if (c == ')' && top == '(') ..., build a tiny map ) → (, ] → [, } → {. On a closer, look up its required opener and compare against the popped value in one line. Cleaner, and it generalises if more pair types appear.

The O(1) early reject. A balanced string has even length — every bracket is half of a pair. If s.length() is odd you can return false before scanning a single character. Small, but it signals you think about invariants.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "{[()]}"

Array state

c='{'

push '{'

top ↓

{

[0]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Stack — One Pass (Optimal) — optimal

6 teaching notes

1
public boolean isBalanced(String s) {
2
    // Odd length can never pair up — O(1) early reject.
3
    if (s.length() % 2 != 0) return false;
4
    // Closer → required opener, so matching is one comparison instead of a chain of
5
    // ifs.
6
    Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
7
    // ArrayDeque is the modern stack in Java — faster than the legacy Stack class.
8
    Deque<Character> stack = new ArrayDeque<>();
9
    for (char c : s.toCharArray()) {
10
        if (c == '(' || c == '[' || c == '{') {
11
            // Openers go on the stack to wait for their partner.
12
            stack.push(c);
13
        } else {
14
            // Check empty FIRST (stray closer), then pop and compare (wrong pair).
15
            // Short-circuit avoids popping an empty stack.
16
            if (stack.isEmpty() || stack.pop() != match.get(c)) {
17
                return false;
18
            }
19
        }
20
    }
21
    // Leftover openers like '(((' mean unbalanced — this final check is the one people
22
    // forget.
23
    return stack.isEmpty();
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The stack literally is the list of currently-open brackets, innermost on top. Reading the stack at any moment tells you exactly which scopes are still open — that's why the same pattern simulates nested function calls, HTML/XML tag validation, and depth tracking in parsers.

ComplexityO(n) time, O(n) space — Each character is pushed at most once and popped at most once → O(n) total work. The stack holds at most n/2 openers → O(n) space.

E · Edge cases and pitfalls6s = "]" — First char is a closer with an empty stack → return false without popping. The stack.isEmpty() guard prevents a crash.Explore edge cases

Edge cases handled

s = "]"First char is a closer with an empty stack → return false without popping. The stack.isEmpty() guard prevents a crash.
s = "((("Three pushes, no closer, loop ends with a non-empty stack → final isEmpty() check returns false.
s = "([)]"')' arrives with '[' on top → match.get(')') is '(' ≠ '[' → false. Interleaving is caught automatically.

Pitfalls

Popping before checking the stack is empty — crashes on a stray closer like ']'.
Omitting the final empty check — '(((' slips through as 'balanced'.
Using a chain of equality ifs instead of a closer→opener map — verbose and bug-prone.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isBalanced(String s) { if (s.length() % 2 != 0) return false; Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{'); Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the end-of-scan empty check

A string of only openers, like '(((', never triggers a mismatch — the bug only shows up if you verify the stack is empty after the loop.

Explore the code comparison

Don't write this

for (char c : s.toCharArray()) {
    // ... push / pop logic ...
}
return true;  // wrong: ignores leftover openers

Write this instead

for (char c : s.toCharArray()) {
    // ... push / pop logic ...
}
return stack.isEmpty();  // leftover openers → unbalanced

Popping before checking emptiness

A closer arriving first (']' or ')(' ) means the stack is empty. Calling pop() on it throws NoSuchElementException in Java and IndexError in Python.

Explore the code comparison

Don't write this

if stack.pop() != match[c]:  # crashes when stack is empty
    return False

Write this instead

if not stack or stack.pop() != match[c]:
    return False

Hard-coded if-chain instead of a map

Manually pairing each closer with each opener is verbose and easy to get wrong; a closer→opener map reduces it to a single lookup and comparison.

Explore the code comparison

Don't write this

if (c == ')' && top == '(') ok = true;
else if (c == ']' && top == '[') ok = true;
else if (c == '}' && top == '{') ok = true;

Write this instead

if (stack.isEmpty() || stack.pop() != match.get(c)) return false;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack for nested / last-opened-first-closed matching

Code pattern to memorize

stack = []
for c in s:
    if c is opener: stack.push(c)
    else:  # closer
        if stack empty or stack.pop() != match(c): return false
return stack.isEmpty()

Rules to remember

1Three failure modes, all must be checked: wrong match, closer with an empty stack, and leftover openers at the end.
2On a closer, an empty stack means a closer with no partner — return false immediately, don't pop.
3Map each closer to its opener ()→(, ]→[, }→{) so the match is one comparison, not a chain of ifs.
4The stack must be empty at the end. "(((" never hits a mismatch but is still unbalanced.
5Odd length can be rejected in O(1) — an odd number of characters can never pair up.

Use this pattern when

Matching nested pairs where the most recent open must close first
Validating brackets, tags, or any LIFO 'open then close' structure
Parsing / expression evaluation where you track depth
Any 'undo the last thing first' requirement

Choose another pattern when

Only ONE type of bracket → a single counter (int) beats a stack, O(1) space
Pairs can close in any order, not LIFO → counting, not a stack
No nesting at all → simple equality of open/close counts

Interview takeaway

A stack is the data structure for 'the most recently opened thing must close first'. Once you see brackets, HTML tags, or nested scopes, reach for it — the same shape powers Min Stack, Valid Parentheses, and recursive-call simulation.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Stack for LIFO matching. Reach for it whenever the most recently opened item must be the first one closed — brackets, HTML/XML tags, nested scopes, undo stacks. Same shape as Valid Parentheses, Min Stack, and recursive-call simulation.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Parentheses
The identical problem on LeetCode — same stack, same three failure modes.
Minimum Remove to Make Valid Parentheses
Coming soon
Track indices of unmatched brackets on the stack, then delete them.
Minimum Add to Make Parentheses Valid
Coming soon
Two counters suffice when there's only one bracket type — the anti-signal in action.
Longest Valid Parentheses
Coming soon
Push indices, not characters, to measure the length of matched runs.

Same pattern

←

Simplify Path

Continue · Next problem

Queue Using Two Stacks

easyStack QueueAsked very often

Balanced Brackets

Stack & Queue · 8 of 17 · 8 min

A bracket is any one of (, ), {, }, [, or ]. Two brackets are a matched pair when an opening bracket occurs to the left of a closing bracket of the exact same type.

Return true if balanced, false otherwise.

In plain English

Examples

Example 1

Input: s = "{[()]}"
Output: true
Note: Perfectly nested: ( ) closes, then [ ] closes, then { } closes — stack drains cleanly.

Example 2

Input: s = "([)]"
Output: false
Note: The ')' arrives while '[' is on top of the stack. ')' expects '(' but sees '[' → mismatch.

Example 3

Input: s = "((("
Output: false
Note: No mismatch ever occurs, but three openers are left on the stack at the end → unbalanced.

Constraints

1 ≤ s.length ≤ 10⁵
s consists only of the characters ()[]{}
An empty inner sequence is fine — '()' is balanced
Return a boolean (some variants ask for the string 'YES'/'NO')

Clarifying questions4First question: Can the string contain characters other than the six brackets?Explore questions

Q1.Can the string contain characters other than the six brackets?
Per the constraints, no. If it could, decide whether to ignore non-brackets or reject — say it out loud.
Q2.Is the empty string balanced?
Conventionally yes (nothing is unmatched), but the constraint here says length ≥ 1, so you won't hit it. Confirm the convention anyway.
Q3.Do different bracket types interleave, like '([)]'?
That is NOT balanced — the ')' tries to close a '[' that is still open. The stack catches this automatically.
Q4.Return a boolean or a 'YES'/'NO' string?
Depends on the platform. The logic is identical; just format the output at the end.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise LIFO matching and pick a stack — and whether you remember all three ways the string can be invalid, not just a wrong-pair mismatch.

Where candidates slip

Forgetting to check the stack is empty at the end (so '(((' passes), or popping from an empty stack on a stray closer like ']'.

How to stand out

Mention the O(1) odd-length rejection, map closers to openers instead of a chain of ifs, and name the LIFO insight explicitly.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Repeated Pair Deletion	`O(n²)`	`O(n)`	Mention it to show you understand the structure, then immediately note it is O(n²) and reach for the stack.	Read
2	Stack — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'the most recent opener must match this closer' — LIFO — not just 'use a stack'.	Read

The decision each character triggers

How to read it:Openers always push. Closers branch into three checks — this is the whole algorithm.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Repeated Pair Deletion

TimeO(n²)SpaceO(n)

Mention it to show you understand the structure, then immediately note it is O(n²) and reach for the stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A balanced string can always be collapsed by repeatedly removing an innermost empty pair like '()', '[]', or '{}'. What's left after removing all of them?

2Hint 2Explore hint

Keep replacing every occurrence of '()', '[]', '{}' with nothing, in a loop, until the string stops changing.

3Hint 3Explore hint

If the final string is empty, it was balanced. If something non-empty remains, it wasn't. Each full pass is O(n) and you may need O(n) passes.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "{[()]}"

Array state

start

original string

{

[0]

[

[1]

(

[2]

)

[3]

]

[4]

}

[5]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isBalanced(String s) { String prev; do { prev = s; s = s.replace("()", "").replace("[]", "").replace("{}", "");Explore the full code

solution.javaJava

Brute Force — Repeated Pair Deletion — reference

4 teaching notes

1
public boolean isBalanced(String s) {
2
    String prev;
3
    do {
4
        // Remember the string before this pass so we can detect when nothing changes.
5
        prev = s;
6
        // Strip every adjacent empty pair. Each replace is O(n) and builds a new
7
        // string.
8
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
9
    // Keep looping until a full pass removes nothing — that's the fixed point.
10
    } while (!s.equals(prev));
11
    // Empty means every bracket was paired away → balanced.
12
    return s.isEmpty();
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Doing a single replace pass instead of looping — '{[]}' wouldn't fully collapse.Explore edge cases

Pitfalls

Doing a single replace pass instead of looping — '{[]}' wouldn't fully collapse.
Using this on large inputs — O(n²) times out at n = 10⁵.
Forgetting that string replace allocates a new string each time, hiding extra cost.

03.2

Approach 2 of 2 · Optimal

Stack — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'the most recent opener must match this closer' — LIFO — not just 'use a stack'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When you see a closing bracket, which opening bracket must it match? The one opened most recently and not yet closed. What structure gives you 'most recent, not yet handled' in O(1)?

2Hint 2Explore hint

Push every opener onto a stack. On a closer, the correct partner is whatever is on top — pop it and verify it's the right type.

3Hint 3Explore hint

Three ways to fail: the stack is empty when a closer arrives (no partner), the popped opener is the wrong type (mismatch), or the stack is non-empty at the end (unclosed openers).

A · Core idea

Why three separate failure checks, not one. A balanced string can break in three distinct ways, and a correct solution catches all three:

Stray closer: "]" or ")(". A closer arrives but the stack is empty — there is no opener to match. If you blindly pop() here, Java throws and Python errors. Check empty before popping.
Wrong pair: "(]". The stack top is ( but the closer is ]. Pop, compare types, fail on mismatch.
Leftover openers: "(((". No mismatch ever happens, but the loop ends with three ( still on the stack. The final stack.isEmpty() check is the only thing that catches this — forgetting it is the single most common bug on this problem.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

s = "{[()]}"

Array state

c='{'

push '{'

top ↓

{

[0]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Stack — One Pass (Optimal) — optimal

6 teaching notes

1
public boolean isBalanced(String s) {
2
    // Odd length can never pair up — O(1) early reject.
3
    if (s.length() % 2 != 0) return false;
4
    // Closer → required opener, so matching is one comparison instead of a chain of
5
    // ifs.
6
    Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
7
    // ArrayDeque is the modern stack in Java — faster than the legacy Stack class.
8
    Deque<Character> stack = new ArrayDeque<>();
9
    for (char c : s.toCharArray()) {
10
        if (c == '(' || c == '[' || c == '{') {
11
            // Openers go on the stack to wait for their partner.
12
            stack.push(c);
13
        } else {
14
            // Check empty FIRST (stray closer), then pop and compare (wrong pair).
15
            // Short-circuit avoids popping an empty stack.
16
            if (stack.isEmpty() || stack.pop() != match.get(c)) {
17
                return false;
18
            }
19
        }
20
    }
21
    // Leftover openers like '(((' mean unbalanced — this final check is the one people
22
    // forget.
23
    return stack.isEmpty();
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each character is pushed at most once and popped at most once → O(n) total work. The stack holds at most n/2 openers → O(n) space.

E · Edge cases and pitfalls6s = "]" — First char is a closer with an empty stack → return false without popping. The stack.isEmpty() guard prevents a crash.Explore edge cases

Edge cases handled

s = "]"First char is a closer with an empty stack → return false without popping. The stack.isEmpty() guard prevents a crash.
s = "((("Three pushes, no closer, loop ends with a non-empty stack → final isEmpty() check returns false.
s = "([)]"')' arrives with '[' on top → match.get(')') is '(' ≠ '[' → false. Interleaving is caught automatically.

Pitfalls

Popping before checking the stack is empty — crashes on a stray closer like ']'.
Omitting the final empty check — '(((' slips through as 'balanced'.
Using a chain of equality ifs instead of a closer→opener map — verbose and bug-prone.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the end-of-scan empty check

A string of only openers, like '(((', never triggers a mismatch — the bug only shows up if you verify the stack is empty after the loop.

Explore the code comparison

Don't write this

for (char c : s.toCharArray()) {
    // ... push / pop logic ...
}
return true;  // wrong: ignores leftover openers

Write this instead

for (char c : s.toCharArray()) {
    // ... push / pop logic ...
}
return stack.isEmpty();  // leftover openers → unbalanced

Popping before checking emptiness

A closer arriving first (']' or ')(' ) means the stack is empty. Calling pop() on it throws NoSuchElementException in Java and IndexError in Python.

Explore the code comparison

Don't write this

if stack.pop() != match[c]:  # crashes when stack is empty
    return False

Write this instead

if not stack or stack.pop() != match[c]:
    return False

Hard-coded if-chain instead of a map

Manually pairing each closer with each opener is verbose and easy to get wrong; a closer→opener map reduces it to a single lookup and comparison.

Explore the code comparison

Don't write this

if (c == ')' && top == '(') ok = true;
else if (c == ']' && top == '[') ok = true;
else if (c == '}' && top == '{') ok = true;

Write this instead

if (stack.isEmpty() || stack.pop() != match.get(c)) return false;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack for nested / last-opened-first-closed matching

Code pattern to memorize

stack = []
for c in s:
    if c is opener: stack.push(c)
    else:  # closer
        if stack empty or stack.pop() != match(c): return false
return stack.isEmpty()

Rules to remember

1Three failure modes, all must be checked: wrong match, closer with an empty stack, and leftover openers at the end.
2On a closer, an empty stack means a closer with no partner — return false immediately, don't pop.
3Map each closer to its opener ()→(, ]→[, }→{) so the match is one comparison, not a chain of ifs.
4The stack must be empty at the end. "(((" never hits a mismatch but is still unbalanced.
5Odd length can be rejected in O(1) — an odd number of characters can never pair up.

Use this pattern when

Matching nested pairs where the most recent open must close first
Validating brackets, tags, or any LIFO 'open then close' structure
Parsing / expression evaluation where you track depth
Any 'undo the last thing first' requirement

Choose another pattern when

Only ONE type of bracket → a single counter (int) beats a stack, O(1) space
Pairs can close in any order, not LIFO → counting, not a stack
No nesting at all → simple equality of open/close counts

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Valid Parentheses
The identical problem on LeetCode — same stack, same three failure modes.
Minimum Remove to Make Valid Parentheses
Coming soon
Track indices of unmatched brackets on the stack, then delete them.
Minimum Add to Make Parentheses Valid
Coming soon
Two counters suffice when there's only one bracket type — the anti-signal in action.
Longest Valid Parentheses
Coming soon
Push indices, not characters, to measure the length of matched runs.

Same pattern

←

Simplify Path

Continue · Next problem

Queue Using Two Stacks