Loading…

easyStack QueueLC #20Asked very often

Valid Parentheses

Q: How do you solve Valid Parentheses using the Repeated String Replacement (Baseline) approach?

When to use it: A cute brute force to mention as the naive idea, then reject for its quadratic cost. Repeatedly delete adjacent matched pairs (`()`, `[]`, `{}`). A fully valid string collapses to empty; anything left over means an unmatched or mis-nested bracket. **Why mention it.** It illustrates the nesting intuition concretely — innermost pairs resolve first — and is a legitimate (if slow) solution. **Why we don't ship it.** String mutation plus repeated full scans is `O(n²)` and allocates new strings each pass. The stack achieves the same logic in one linear pass. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Valid Parentheses using the Stack — One Pass (Optimal) approach?

When to use it: The answer they want. Say 'a stack models last-opened-first-closed' before writing it. Scan the string left to right with a stack of unmatched opening brackets. **Why a stack.** Nesting imposes a last-in-first-out discipline: the bracket that opened most recently is the one that must close next. A stack is the data structure whose `push`/`pop` are exactly that discipline, so it mirrors the problem with no bookkeeping. **The two cases per character.** If the character is an **opener** (`(`, `[`, `{`), push it — it's now the innermost context awaiting closure. If it's a **closer**, it must resolve against the most recent opener: peek/pop the top and check it's the matching opener (`)`→`(`, `]`→`[`, `}`→`{`). Mapping *closer → opener* lets this be a single equality check. **The three ways to fail.** (1) A closer arrives with an **empty stack** — there's no opener to match, invalid. (2) The popped top is the **wrong type** — e.g. `]` on top of `(`, which also rejects mis-nesting like `([)]`. (3) The scan finishes but the **stack is non-empty** — some openers were never closed (`(((`). Only if none of these happen is the string valid. **Why a counter isn't enough.** With a single bracket type you could just track a balance counter. But three types interact through *order*: `([)]` has matching counts yet is invalid. The stack records *which* type is open and in what nesting order, so it catches type/order errors a counter cannot. **Early termination.** We can `return false` the instant any check fails, so invalid strings often exit before reading everything — though worst-case (all valid or failing at the end) is still O(n). Time complexity: O(n). Space complexity: O(n).

LCPractice

Stack & Queue · 1 of 17 · 8 min

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1
Open brackets must be closed by the same type of brackets.
2
Open brackets must be closed in the correct order.
3
Every close bracket has a corresponding open bracket of the same type.

In plain English

Validity means brackets are properly nested and matched by type. The most recently opened bracket must be the first to close — that 'last in, first out' requirement is precisely what a stack enforces. We track open brackets and resolve each closer against the most recent opener.

Examples

Example 1

Input: s = "()[]{}"
Output: true
Note: Three independent, correctly matched pairs.

Example 2

Input: s = "([)]"
Output: false
Note: Counts match but nesting is wrong — ')' tries to close '[' . A counter would wrongly accept this; the stack rejects it.

Example 3

Input: s = "(]"
Output: false
Note: ']' tries to close '(' — type mismatch on pop → invalid.

Constraints

1 ≤ s.length ≤ 10⁴
s consists of parentheses only '()[]{}'

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?
No — constraints restrict it to ()[]{}. If other characters were allowed, I'd simply skip them.
Q2.Is an empty string valid?
Constraints say length ≥ 1, but logically an empty string is valid (nothing unbalanced) and the code returns true via the empty stack.
Q3.Do different bracket types interact, or are they independent?
They interact via nesting order — ([)] is invalid even though counts match. That's why a stack (type-aware order) is required, not three counters.
Q4.Could the string start with a closing bracket?
Yes, e.g. ']'. The empty-stack check on a closer catches it and returns false.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Push every opening bracket onto a stack; on each closing bracket, the top of the stack must be its matching opener — pop it, else the string is invalid. The string is valid only if every closer matched and the stack is empty at the end. O(n) time, O(n) space. The stack models 'most recently opened must close first', which is exactly LIFO.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a stack on a nesting problem and handle all three failure modes — wrong type, closer with nothing open, and leftover openers at the end.

Where candidates slip

Using a counter instead of a stack (accepts mismatched types like ([)]), forgetting the empty-stack check before popping, or not verifying the stack is empty at the end.

How to stand out

Name the LIFO insight, enumerate the three ways a string can be invalid up front, and map closers to openers so the inner check is one comparison.

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	Repeated String Replacement (Baseline)	`O(n²)`	`O(n)`	A cute brute force to mention as the naive idea, then reject for its quadratic cost.	Read
2	Stack — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'a stack models last-opened-first-closed' before writing it.	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

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

Repeated String Replacement (Baseline)

TimeO(n²)SpaceO(n)

A cute brute force to mention as the naive idea, then reject for its quadratic cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A valid string must contain at least one innermost pair like () or [] or {}. What if you keep deleting those?

2Hint 2Explore hint

Repeatedly remove every occurrence of "()", "[]", "{}" until nothing changes.

3Hint 3Explore hint

If the string becomes empty it was valid. It works but each removal pass is O(n) and you may need O(n) passes → O(n²).

A · Core idea

Repeatedly delete adjacent matched pairs ((), [], {}). A fully valid string collapses to empty; anything left over means an unmatched or mis-nested bracket.

Why mention it. It illustrates the nesting intuition concretely — innermost pairs resolve first — and is a legitimate (if slow) solution. Why we don't ship it. String mutation plus repeated full scans is O(n²) and allocates new strings each pass. The stack achieves the same logic in one linear pass.

B · Visual dry run

Interactive dry run

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

s = "([])"

pass 1

remove inner '[]' → "()"

State"()"

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean isValid(String s) { int prevLength = -1; while (s.length() != prevLength) { prevLength = s.length(); s = s.replace("()", "").replace("[]", "").replace("{}", "");Explore the full code

solution.javaJava

Repeated String Replacement (Baseline) — reference

3 teaching notes

1
public boolean isValid(String s) {
2
    int prevLength = -1;
3
    // Keep peeling until a pass removes nothing.
4
    while (s.length() != prevLength) {
5
        prevLength = s.length();
6
        // Remove all innermost pairs this pass — O(n) and allocates a new string.
7
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
8
    }
9
    // Valid iff everything cancelled out.
10
    return s.isEmpty();
11
}

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

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

Peeling innermost pairs is exactly what a stack does implicitly: when a closer meets its opener on top, that's an innermost pair being removed — but the stack removes it in O(1) without rescanning.

ComplexityO(n²) time, O(n) space — Each pass scans the whole string O(n); up to n/2 passes are needed as pairs peel off one layer at a time → O(n²).

E · Edge cases and pitfalls2O(n²) time from repeated full-string scans and allocations.Explore edge cases

Pitfalls

O(n²) time from repeated full-string scans and allocations.
Assuming one replacement pass suffices — nested layers need many passes.

03.2

Approach 2 of 2 · Optimal

Stack — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'a stack models last-opened-first-closed' before writing it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When you see a closing bracket, which open bracket does it have to match — the first one you saw or the most recent unmatched one?

2Hint 2Explore hint

Push each opener. On a closer, the correct partner is whatever's on top of the stack; pop and compare.

3Hint 3Explore hint

Reject early if a closer finds an empty stack or a non-matching top. At the end, the stack must be empty.

A · Core idea

Scan the string left to right with a stack of unmatched opening brackets.

Why a stack. Nesting imposes a last-in-first-out discipline: the bracket that opened most recently is the one that must close next. A stack is the data structure whose push/pop are exactly that discipline, so it mirrors the problem with no bookkeeping.

The two cases per character. If the character is an opener ((, [, {), push it — it's now the innermost context awaiting closure. If it's a closer, it must resolve against the most recent opener: peek/pop the top and check it's the matching opener ()→(, ]→[, }→{). Mapping closer → opener lets this be a single equality check.

The three ways to fail. (1) A closer arrives with an empty stack — there's no opener to match, invalid. (2) The popped top is the wrong type — e.g. ] on top of (, which also rejects mis-nesting like ([)]. (3) The scan finishes but the stack is non-empty — some openers were never closed ((((). Only if none of these happen is the string valid.

Why a counter isn't enough. With a single bracket type you could just track a balance counter. But three types interact through order: ([)] has matching counts yet is invalid. The stack records which type is open and in what nesting order, so it catches type/order errors a counter cannot.

Early termination. We can return false the instant any check fails, so invalid strings often exit before reading everything — though worst-case (all valid or failing at the end) is still O(n).

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 isValid(String s) {
2
    // ArrayDeque is the recommended stack in Java — faster than the legacy Stack class.
3
    Deque<Character> stack = new ArrayDeque<>();
4
    // Closer → opener, so the closer branch is one equality check.
5
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
6
    for (char c : s.toCharArray()) {
7
        if (pairs.containsKey(c)) {            // closer
8
            // Short-circuit: empty stack OR wrong top → invalid. The || order avoids
9
            // popping an empty stack.
10
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
11
                return false;
12
            }
13
        } else {                              // opener
14
            // Opener becomes the new innermost context.
15
            stack.push(c);
16
        }
17
    }
18
    // Leftover openers → unclosed → invalid.
19
    return stack.isEmpty();
20
}

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

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

The stack turns 'remember the context I must return to' into O(1) push/pop. That framing — push when you enter a nested scope, pop when you leave it — recurs in expression evaluation, the call stack itself, HTML/XML tag validation, and Min Stack. Whenever a problem says 'properly nested', think stack first.

ComplexityO(n) time, O(n) space — Each character is pushed and popped at most once → O(n) time. The stack can hold up to n openers (e.g. "(((((") → O(n) space.

E · Edge cases and pitfalls8s = "]" — Closer with empty stack → return false immediately.Explore edge cases

Edge cases handled

s = "]"Closer with empty stack → return false immediately.
s = "("Opener pushed, loop ends, stack non-empty → false.
s = "([)]"')' pops '[' → type mismatch → false. Stack catches the mis-nesting a counter would miss.
s = "()[]{}"Each closer matches and pops; stack empty at the end → true.

Pitfalls

Popping before checking the stack is non-empty — exception on a leading closer.
Forgetting the final emptiness check — accepts unclosed openers like '((('.
Using a counter instead of a stack — accepts mismatched types ([)].
Mapping opener→closer and then writing awkward reverse lookups.

Practice

Try the solution yourself

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

Editable code previewpublic boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{'); for (char c : s.toCharArray()) { if (pairs.containsKey(c)) { // closerExplore 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.

Counter instead of stack

Counting open vs close ignores type and nesting order, so '([)]' (equal counts, wrong nesting) is wrongly accepted. You must track which type is open, which a stack does.

Explore the code comparison

Don't write this

bal = 0
for c in s:
    if c in '([{': bal += 1
    else: bal -= 1
    if bal < 0: return False
return bal == 0

Write this instead

stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in s:
    if c in pairs:
        if not stack or stack.pop() != pairs[c]:
            return False
    else:
        stack.append(c)
return not stack

Popping an empty stack

If a closing bracket appears with no open bracket pending, popping throws (Java) or errors (Python). Always test emptiness before popping.

Explore the code comparison

Don't write this

for (char c : s.toCharArray()) {
    if (pairs.containsKey(c)) {
        if (stack.pop() != pairs.get(c)) return false; // pop() on empty throws
    } else {
        stack.push(c);
    }
}

Write this instead

for (char c : s.toCharArray()) {
    if (pairs.containsKey(c)) {
        if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
    } else {
        stack.push(c);
    }
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

LIFO matching with a stack

Code pattern to memorize

stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for c in s:
    if c in pairs:                       # closer
        if not stack or stack.pop() != pairs[c]: return False
    else:                                # opener
        stack.append(c)
return not stack

Rules to remember

1Push openers, and on a closer check the stack top is its exact match before popping.
2A closer with an empty stack → invalid immediately (nothing to close).
3At the end, the stack must be empty — leftover openers mean unclosed brackets.
4Map closer→opener (not opener→closer) so the closer branch is a single pop() == map[c] check.
5Three bracket types means matching by type, not just count — a counter alone passes ([)], which is wrong.

Use this pattern when

Balanced/nested structure validation: brackets, tags, scopes
'Most recent unmatched thing must resolve first' (LIFO) situations
Parsing where you need to remember a context to return to

Choose another pattern when

Single bracket type and you only need a yes/no count → an integer counter is O(1) space
Order doesn't matter, only totals → counting, not a stack
You need all matchings/positions, not just validity → augment the stack to store indices

Interview takeaway

A stack is the natural model for nesting: the last thing opened is the first that must close. Recognising 'nested / balanced' as a LIFO problem is the reusable insight behind expression parsing, the min-stack, and RPN evaluation.

Continue

Transfer the pattern to another problem

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

Transferable patternStack for balanced/nested structure validation. Reach for it whenever 'most recently opened must close first' (LIFO) applies — brackets, tags, scopes. Same family as Min Stack, Evaluate RPN, and expression parsing.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Generate Parentheses
Produce all valid combinations via backtracking with open/close counts.
Longest Valid Parentheses
Coming soon
Stack of indices (or DP) to measure the longest balanced run.
Minimum Remove to Make Valid Parentheses
Coming soon
Stack of indices; remove the unmatched positions at the end.
Minimum Add to Make Parentheses Valid
Coming soon
Single type → a counter of unmatched opens and closes suffices.

Same pattern

Continue · Next problem

Min Stack

easyStack QueueLC #20Asked very often

Valid Parentheses

LCPractice

Stack & Queue · 1 of 17 · 8 min

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1
Open brackets must be closed by the same type of brackets.
2
Open brackets must be closed in the correct order.
3
Every close bracket has a corresponding open bracket of the same type.

In plain English

Examples

Example 1

Input: s = "()[]{}"
Output: true
Note: Three independent, correctly matched pairs.

Example 2

Input: s = "([)]"
Output: false
Note: Counts match but nesting is wrong — ')' tries to close '[' . A counter would wrongly accept this; the stack rejects it.

Example 3

Input: s = "(]"
Output: false
Note: ']' tries to close '(' — type mismatch on pop → invalid.

Constraints

1 ≤ s.length ≤ 10⁴
s consists of parentheses only '()[]{}'

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?
No — constraints restrict it to ()[]{}. If other characters were allowed, I'd simply skip them.
Q2.Is an empty string valid?
Constraints say length ≥ 1, but logically an empty string is valid (nothing unbalanced) and the code returns true via the empty stack.
Q3.Do different bracket types interact, or are they independent?
They interact via nesting order — ([)] is invalid even though counts match. That's why a stack (type-aware order) is required, not three counters.
Q4.Could the string start with a closing bracket?
Yes, e.g. ']'. The empty-stack check on a closer catches it and returns false.

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 reach for a stack on a nesting problem and handle all three failure modes — wrong type, closer with nothing open, and leftover openers at the end.

Where candidates slip

Using a counter instead of a stack (accepts mismatched types like ([)]), forgetting the empty-stack check before popping, or not verifying the stack is empty at the end.

How to stand out

Name the LIFO insight, enumerate the three ways a string can be invalid up front, and map closers to openers so the inner check is one comparison.

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	Repeated String Replacement (Baseline)	`O(n²)`	`O(n)`	A cute brute force to mention as the naive idea, then reject for its quadratic cost.	Read
2	Stack — One Pass (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Say 'a stack models last-opened-first-closed' before writing it.	Read

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

Repeated String Replacement (Baseline)

TimeO(n²)SpaceO(n)

A cute brute force to mention as the naive idea, then reject for its quadratic cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A valid string must contain at least one innermost pair like () or [] or {}. What if you keep deleting those?

2Hint 2Explore hint

Repeatedly remove every occurrence of "()", "[]", "{}" until nothing changes.

3Hint 3Explore hint

If the string becomes empty it was valid. It works but each removal pass is O(n) and you may need O(n) passes → O(n²).

A · Core idea

Repeatedly delete adjacent matched pairs ((), [], {}). A fully valid string collapses to empty; anything left over means an unmatched or mis-nested bracket.

B · Visual dry run

Interactive dry run

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

s = "([])"

pass 1

remove inner '[]' → "()"

State"()"

Final resulttrue

C · Code with teaching comments

solution.javaJava

Repeated String Replacement (Baseline) — reference

3 teaching notes

1
public boolean isValid(String s) {
2
    int prevLength = -1;
3
    // Keep peeling until a pass removes nothing.
4
    while (s.length() != prevLength) {
5
        prevLength = s.length();
6
        // Remove all innermost pairs this pass — O(n) and allocates a new string.
7
        s = s.replace("()", "").replace("[]", "").replace("{}", "");
8
    }
9
    // Valid iff everything cancelled out.
10
    return s.isEmpty();
11
}

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

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

Peeling innermost pairs is exactly what a stack does implicitly: when a closer meets its opener on top, that's an innermost pair being removed — but the stack removes it in O(1) without rescanning.

ComplexityO(n²) time, O(n) space — Each pass scans the whole string O(n); up to n/2 passes are needed as pairs peel off one layer at a time → O(n²).

E · Edge cases and pitfalls2O(n²) time from repeated full-string scans and allocations.Explore edge cases

Pitfalls

O(n²) time from repeated full-string scans and allocations.
Assuming one replacement pass suffices — nested layers need many passes.

03.2

Approach 2 of 2 · Optimal

Stack — One Pass (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Say 'a stack models last-opened-first-closed' before writing it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

When you see a closing bracket, which open bracket does it have to match — the first one you saw or the most recent unmatched one?

2Hint 2Explore hint

Push each opener. On a closer, the correct partner is whatever's on top of the stack; pop and compare.

3Hint 3Explore hint

Reject early if a closer finds an empty stack or a non-matching top. At the end, the stack must be empty.

A · Core idea

Scan the string left to right with a stack of unmatched opening brackets.

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 isValid(String s) {
2
    // ArrayDeque is the recommended stack in Java — faster than the legacy Stack class.
3
    Deque<Character> stack = new ArrayDeque<>();
4
    // Closer → opener, so the closer branch is one equality check.
5
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
6
    for (char c : s.toCharArray()) {
7
        if (pairs.containsKey(c)) {            // closer
8
            // Short-circuit: empty stack OR wrong top → invalid. The || order avoids
9
            // popping an empty stack.
10
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
11
                return false;
12
            }
13
        } else {                              // opener
14
            // Opener becomes the new innermost context.
15
            stack.push(c);
16
        }
17
    }
18
    // Leftover openers → unclosed → invalid.
19
    return stack.isEmpty();
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 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 and popped at most once → O(n) time. The stack can hold up to n openers (e.g. "(((((") → O(n) space.

E · Edge cases and pitfalls8s = "]" — Closer with empty stack → return false immediately.Explore edge cases

Edge cases handled

s = "]"Closer with empty stack → return false immediately.
s = "("Opener pushed, loop ends, stack non-empty → false.
s = "([)]"')' pops '[' → type mismatch → false. Stack catches the mis-nesting a counter would miss.
s = "()[]{}"Each closer matches and pops; stack empty at the end → true.

Pitfalls

Popping before checking the stack is non-empty — exception on a leading closer.
Forgetting the final emptiness check — accepts unclosed openers like '((('.
Using a counter instead of a stack — accepts mismatched types ([)].
Mapping opener→closer and then writing awkward reverse lookups.

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.

Counter instead of stack

Counting open vs close ignores type and nesting order, so '([)]' (equal counts, wrong nesting) is wrongly accepted. You must track which type is open, which a stack does.

Explore the code comparison

Don't write this

bal = 0
for c in s:
    if c in '([{': bal += 1
    else: bal -= 1
    if bal < 0: return False
return bal == 0

Write this instead

stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for c in s:
    if c in pairs:
        if not stack or stack.pop() != pairs[c]:
            return False
    else:
        stack.append(c)
return not stack

Popping an empty stack

If a closing bracket appears with no open bracket pending, popping throws (Java) or errors (Python). Always test emptiness before popping.

Explore the code comparison

Don't write this

for (char c : s.toCharArray()) {
    if (pairs.containsKey(c)) {
        if (stack.pop() != pairs.get(c)) return false; // pop() on empty throws
    } else {
        stack.push(c);
    }
}

Write this instead

for (char c : s.toCharArray()) {
    if (pairs.containsKey(c)) {
        if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
    } else {
        stack.push(c);
    }
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

LIFO matching with a stack

Code pattern to memorize

stack = []
pairs = {')':'(', ']':'[', '}':'{'}
for c in s:
    if c in pairs:                       # closer
        if not stack or stack.pop() != pairs[c]: return False
    else:                                # opener
        stack.append(c)
return not stack

Rules to remember

1Push openers, and on a closer check the stack top is its exact match before popping.
2A closer with an empty stack → invalid immediately (nothing to close).
3At the end, the stack must be empty — leftover openers mean unclosed brackets.
4Map closer→opener (not opener→closer) so the closer branch is a single pop() == map[c] check.
5Three bracket types means matching by type, not just count — a counter alone passes ([)], which is wrong.

Use this pattern when

Balanced/nested structure validation: brackets, tags, scopes
'Most recent unmatched thing must resolve first' (LIFO) situations
Parsing where you need to remember a context to return to

Choose another pattern when

Single bracket type and you only need a yes/no count → an integer counter is O(1) space
Order doesn't matter, only totals → counting, not a stack
You need all matchings/positions, not just validity → augment the stack to store indices

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

Generate Parentheses
Produce all valid combinations via backtracking with open/close counts.
Longest Valid Parentheses
Coming soon
Stack of indices (or DP) to measure the longest balanced run.
Minimum Remove to Make Valid Parentheses
Coming soon
Stack of indices; remove the unmatched positions at the end.
Minimum Add to Make Parentheses Valid
Coming soon
Single type → a counter of unmatched opens and closes suffices.

Same pattern

Continue · Next problem

Min Stack