vizlearn

Valid parentheses

Interview QuestionsBy Updated

A stack. Push every opener; on a closer, pop and check it matches. Two things fail: a closer with nothing to match, and a closer matching the wrong opener. A third check at the end catches openers that were never closed — miss it and "(((" passes.

Overview

Why a stack and not a counter

With one bracket type, counting works: increment on open, decrement on close, fail if it goes negative or ends non-zero. With several types it does not — "([)]" has balanced counts and is wrong.

A stack captures the thing a counter loses: not just how many are open, but which, and in what order. Nesting is inherently last-in-first-out, which is exactly what a stack is.

StringsCoding problemEasy

Step through it

What to watch

  • The stack depth is the current nesting level.
  • A match pops; a mismatch stops immediately.
  • The final empty-stack check is what rejects "(((".

Say this out loud

"Stack. Push openers, pop and compare on closers, and at the end the stack must be empty. Three failure modes: wrong match, closer with an empty stack, and leftovers at the end."

Valid parentheses

Check whether a string of brackets is balanced.

The three failure modes

Mismatch. The popped opener does not correspond to the closer. "(]".

Empty stack on a closer. A closer arrived with nothing open. ")(" — and forgetting this check gives an IndexError rather than a False.

Non-empty stack at the end. Openers never closed. "(((" passes every in-loop check and is still unbalanced.

What it generalises to

This is the shape of every nesting problem: matching HTML tags, checking JSON structure, the call stack itself, and the shunting-yard algorithm that turns infix expressions into postfix. Once you see "most recent unclosed thing" in a problem, the answer is a stack.

Run it in Python

The matcher with its stack printed at each step, run over inputs chosen so each of the three failure modes fires once, and a counter-based version that gets one of them wrong.

parentheses.pyPython 3
Output
How the code works
  1. stack.append(ch)Openers are remembered in order. The stack's top is always the most recent unclosed bracket, which is the only one a closer is allowed to match.
  2. if not stack: return FalseA closer with nothing open. Skipping this check does not give a wrong answer — it gives an IndexError, which is worse in an interview.
  3. if stack.pop() != PAIRS[ch]:Pop and compare in one step. The dictionary maps each closer to the opener it requires, which keeps the check to a single comparison.
  4. if stack: return FalseThe check people forget. "(((" passes every in-loop test and is still unbalanced.
Change one thing
  • Delete the final if stack: and run "(((". It reports balanced — the exact bug the check exists for.
  • Extend it to HTML tags: push <div>, pop on </div>. Same algorithm, and now it is a parser.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why is a counter not enough for multiple bracket types?
  2. Which input passes every in-loop check and is still unbalanced?
  3. Forgetting the empty-stack check before popping gives you:





 Cheat sheet
Valid parentheses
A stack. Push every opener; on a closer, pop and check it matches. Two things fail: a closer with nothing to match, and a closer matching the wrong opener. A third check at the end catches openers that were never closed — miss it and "(((" passes.
INTERVIEW · vizlearn.in/interview/valid-parentheses.html
More in Interview
InterviewRun-length string compressionInterviewLongest common prefixInterviewImplement substring search (strStr)InterviewIsomorphic strings
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact