Give a candidate the string "([)]" and ask whether the brackets are balanced. The ones who answer fast almost never count brackets. They track what’s still open and check every closer against the most recent opener. That instinct is the whole problem, and it’s why interviewers keep Valid Parentheses around as a two-minute warm-up before the real question starts.
The problem itself (LeetCode 20) is small: a string of ()[]{}, return true if every opener has a matching closer of the same type, closed in the right order. Empty string is valid. "()[]{}" is valid. "(]" and "([)]" are not. What the interviewer is reading off your screen is whether you pick the right data structure without being told, and whether you handle the two failure cases that trip most people.
Why counting brackets falls apart
The tempting first idea is a counter. See an open bracket, add one; see a close, subtract one; if you never go negative and land on zero, call it balanced. That works for exactly one situation: a single kind of bracket. The moment you mix (), [], and {}, a counter can’t tell you whether the closer you just hit matches the opener it’s closing. Look at "([)]": two opens, two closes, the count returns to zero, and the string is still invalid because the nesting crosses.
Three counters, one per bracket type, fail the same way. "([)]" keeps all three counts balanced while the order is wrong. The piece of information you keep throwing away is which bracket is the most recent unclosed one. You need the last thing you opened, then the thing before that, in reverse order. A structure that hands you items back in reverse order of insertion is a stack, so the problem is choosing itself for you.
The stack does the bookkeeping for you
Walk the string left to right. Every time you see an opener, push it. Every time you see a closer, the only opener it’s allowed to match is the one on top of the stack. If the top matches, pop it and keep going. If it doesn’t match, or there’s nothing on top to match against, the string is invalid. When you reach the end, the stack has to be empty; anything left over is an opener that never got closed.
def is_valid(s: str) -> bool:
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs: # ch is a closer
if not stack or stack.pop() != pairs[ch]:
return False
else: # ch is an opener
stack.append(ch)
return not stack
Keying the map on closers is the small move that keeps this readable. ch in pairs asks “is this a closing bracket,” and pairs[ch] hands back the exact opener it needs to see on top. No per-type branching, no six-way if-else ladder. One pass gives O(n) time; the stack can hold up to n items on an input like "(((((", so O(n) space in the worst case.
The edge cases interviewers poke at
Two inputs separate a working solution from a nearly-working one. The first is a closer with nothing open, like ")" on its own, or "()]" once the pair has popped. The not stack guard catches it; drop that guard and stack.pop() throws on an empty list, which reads as someone who didn’t picture the case. The second is leftover openers. A string like "(" or "([]" runs clean through the loop and then has to fail on the final return not stack. People who only test “does it reject a mismatch” forget this one and happily return true for an unclosed string.
The empty string returns true, which catches some people off guard but matches the definition: nothing to close means nothing is unbalanced. If you want a one-line early exit, an odd-length string can never balance, so if len(s) % 2: return False skips the loop. That’s a micro-optimization, not a correctness fix, and saying so out loud is worth more than the line itself. Adding it while missing the empty-stack case is the wrong trade to make under time pressure.
Watch for the single-type variant. If the interviewer restricts input to just ( and ), the counter idea comes back and beats the stack: one integer, increment on open, decrement on close, fail the instant it goes negative, check for zero at the end, O(1) space. Reaching for a stack there isn’t wrong, but noticing that a counter is enough shows you’re matching the tool to the constraints instead of replaying the last problem you memorized.
Where the follow-ups go
Valid Parentheses is rarely the whole interview. It’s the setup, and the follow-up tells you what the interviewer actually wanted to watch. The common next step is Min Stack (155): build a stack that also returns its minimum in O(1). The move is to stop thinking of a stack as holding bare values and start pushing augmented state, either a running minimum next to each value or a second stack that mirrors the minimum at every level. Once you push “this value plus the smallest value beneath it,” getMin is just a peek.
Decode String (394) is the same muscle in a harder shape. Given 3[a2[c]], produce accaccacc. A [ means pause the string you’re building and start a fresh one; a ] means finish the inner string, repeat it, and resume the outer. Two stacks hold what you paused: the repeat counts and the partial strings. Any time a problem has a “do this, but first go handle the nested thing, then come back exactly where you left off” shape, a stack is holding your place in line.
The same instinct runs through Basic Calculator (224), where the stack stores the running result and the sign in front of each parenthesized group, and through Longest Valid Parentheses (32), which trips people because the obvious thing to push is characters when what you actually need is indices, so you can measure the distance between matched positions. That switch, from pushing values to pushing positions, is the one idea that problem is testing.
| Problem | What goes on the stack | The signal it’s a stack problem |
|---|---|---|
| Valid Parentheses (20) | the opener character | match each closer against the most recent opener |
| Min Stack (155) | value plus the running minimum | O(1) access to a property of everything below the top |
| Decode String (394) | repeat count plus string built so far | a token that means pause, do the inner work, resume |
| Basic Calculator (224) | result and sign before a parenthesis | nested sub-expressions you finish and fold back in |
| Longest Valid Parentheses (32) | indices, not characters | you need the distance between matched positions |
The pattern under all of them is narrow enough to name out loud. Reach for a stack when the thing you care about is the most recent unmatched item, or when solving the current step means suspending work, handling something nested, and picking up right where you paused. Valid Parentheses is the cleanest version of the first case, which is exactly why it’s the one they hand you before the problem that actually decides the interview.
Drill the patterns next:
