Valid Parentheses

▣ tips & tricks — read first

what this problem is really testing

stack / LIFOmatching pairsorder matterssingle passhashmap lookupempty-stack & leftover edges

This is the entry exam for the stack pattern. The interviewer is checking whether you recognize that the most recently opened bracket is the only one allowed to close next — and whether you handle the two quiet edges: a closer with nothing to match, and openers left dangling at the end.

mental model

Read each opener as a promise to close later. Promises must be honored in reverse order of how they were made — the last promise first. A stack stores the unkept promises in exactly that order: whatever sits on top is the only promise a closing bracket is permitted to settle.

pattern toolkit — when you see X, reach for Y

Nested / “most recent must close first”

A stack — the last thing opened is the first that may close (LIFO).

Match an item to its partner by type

A close → open hashmap so the check is one O(1) lookup.

A closer appears

Compare it to the top of the stack — never the bottom, never a counter.

Balanced count isn’t enough

You also need type + order — a plain depth counter is blind to both.

Symbols must cancel in reverse order

Push on open, pop on close — the classic stack-matching shape.

Odd total length

Bail immediately — an odd number of brackets can never pair up.

edge-case reflexes — ask before coding

• What if the very first char is a closer? (Stack empty → false, don’t pop nothing.)
• What if openers are left over at the end? (Stack non-empty → false.)
• Do I match on type, not just “a bracket closed”? ((] must fail.)
• Do I match on order? (([)] must fail even though counts balance.)
• Is the length odd? (Instant false — a free early exit.)

The problem

Given a string s of only the six characters ()[]{}, return true when every bracket is closed by the same type and in the correct order, and false otherwise.

input	output	why
()	true	opened, then immediately closed by its own type
()[]{}	true	three independent pairs, one after another
([])	true	inner [ ] closes before the outer ( ) — proper nesting
(]	false	the closer ] does not match the opener (
([)]	false	) tries to close [ — the pairs cross over
)	false	a closer with no opener before it
(	false	an opener that is never closed

Constraints: 1 ≤ s.length ≤ 10⁴, and s contains only ()[]{}.

Mental model — a stack of promises

Every time you see an opener, you make a promise: “I will close this later.” You can open more promises before settling the first — but when a closer comes, it can only settle the most recent open promise. That is last-in, first-out: a stack.

promises ▲

{ ← must close first

[

(

Why a stack — and why a counter is not enough

The tempting shortcut is to count depth: +1 on every opener, −1 on every closer, and declare the string valid if the count never goes negative and ends at 0. It is fast, and it is wrong — a counter knows how many brackets are open but not which type, and it has no memory of order.

Run it on ([)]:

i	char	depth	what the counter ignores
0	(	1	opened — but of which type? counter forgets
1	[	2	opened — order not recorded
2	)	1	closed “something”… actually crossed [ wrongly
3	]	0	closed “something”… ends at 0 → false positive

State evolution

Watch the stack rise and fall as we scan left to right. Two contrasting strings tell the whole story.

([]) → valid

i	char	decision	stack after
0	(	opener → push	(
1	[	opener → push	( [
2	]	top is [ → match → pop	(
3	)	top is ( → match → pop	(empty)
end	—	stack empty → valid	true

stack ▲

[ ← top

(

([)] → invalid

i	char	decision	stack after
0	(	opener → push	(
1	[	opener → push	( [
2	)	top is [ ≠ ( → MISMATCH	reject

stack ▲

[ ← top

(

Interactive walkthrough

Pick a string and press step to scan one character at a time — or hit auto to watch the stack grow and shrink. Green = a matched pop, red = the character that breaks it.

The matching map

Instead of a tangle of if/elif per bracket type, store each closer’s required opener once. One O(1) lookup replaces six comparisons.

pairs = {')': '(', ']': '[', '}': '{'}   # closer → the opener it must match

Implementation

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}   # closer → matching opener
    stack = []

    for ch in s:
        if ch in pairs:                      # ch is a CLOSING bracket
            # pop the expected opener; use '#' as a sentinel if stack is empty
            top = stack.pop() if stack else '#'
            if pairs[ch] != top:
                return False                 # wrong type, wrong order, or nothing to match
        else:                                # ch is an OPENING bracket
            stack.append(ch)

    return not stack                         # valid only if no promise is left unkept

The '#' sentinel is the trick that folds the empty-stack edge into the normal mismatch check: popping from an empty stack yields '#', which can never equal a real opener, so the comparison fails naturally.

Every step is one of four decisions

While scanning, each character triggers exactly one of these. Each is shown on the input that exercises it.

1 · opener → push

The opener is a fresh promise. Push it; the stack grows by one.

( arrives ▲

( ← top

2 · closer matches the top → pop

The closer settles the most recent promise. Pop it; the stack shrinks.

i	char	decision	stack after
0	(	opener → push	(
1	)	top is ( → match → pop	(empty)

before ) ▲

( ← top

3 · closer ≠ top → reject (wrong type/order)

The closer’s required opener is not on top. The promise it tries to settle was never the most recent — invalid.

] arrives ▲

( ← top

4 · closer but the stack is empty → reject

There is no promise to settle. (In code, the pop() returns the '#' sentinel and the comparison fails.)

) arrives ▲

∅ empty

And two ways the scan ends

Reaching the last character does not automatically mean valid — the stack has the final say.

empty stack → valid (true)

Every promise was kept.

stack ▲

∅ empty

leftover openers → invalid (false)

A promise was never settled.

end of ( ▲

( ← top

A free early exit

A valid string pairs every bracket, so its length must be even. If len(s) is odd you can return false before scanning a single character.

input	length	parity	verdict
(()	3	odd	false — no scan needed
(())	4	even	must still scan to confirm

if len(s) % 2:          # odd length can never balance
    return False

Complexity

metric	cost	reason
time	O(n)	one left-to-right pass; each char is pushed and popped at most once
space	O(n)	worst case the stack holds every char — e.g. all openers

Time, counted. For ()() we do exactly 2 pushes + 2 pops over 4 chars — work scales one-to-one with n:

char	op	running ops
(	push	1
)	pop	2
(	push	3
)	pop	4

Space, worst case. A string of only openers never pops, so the stack grows to n:

stack ▲

( ← top

(

(

Pitfalls & pattern recognition