Skip to content
16-Week DSA Roadmap
LeetCode #20EasyProblem 1 of 8

Valid Parentheses

Check whether every bracket in a string is closed by the right kind of bracket, in the right order.

  • Stack for matching pairs

Before this, know: Strings and indexes, What a stack is (push, pop, peek)

The problem in plain English

You get a string s made only of six characters: ( ) [ ] { }. The first of each pair is an opener; the second is a closer. Return true if the brackets are balanced, and false otherwise.

“Balanced” means three things:

  • Every opener is closed by a closer of the same kind: ( by ), [ by ], { by }.
  • Openers are closed in the right order: the one opened most recently is closed first.
  • Every closer has an opener before it, and nothing is left open at the end.

Here is s = "([]{})". Each arc joins an opener to the closer that matches it:

(0[1]2{3}4)5
Balanced: every arc joins a matching pair, and no arcs cross. The [ ] and { } pairs sit neatly inside the ( ).

And here is s = "([)]". The ) arrives while [ is still open, so the pairs would have to cross:

(0[1)2]3
Not balanced: the ) at index 2 tries to close the ( at index 0, but the [ at index 1 is still open in between. Rose means 'no valid partner'.

A few more examples: "()" → true, "()[]{}" → true, "(]" → false, "(()" → false (one ( never closes). The string has between 1 and 10,000 characters.

Before you code: think it through

So when we meet a closer, the only opener that matters is the most recent one that is still open. We need a place to keep openers where the newest one is always the easiest to reach. That is exactly what a stack is: a pile where you only ever add to the top (push), look at the top (peek), or take from the top (pop). Last in, first out.

Pause and think

Read s = "{[]}" from left to right. When you reach the ] at index 2, which opener must it close? And when you reach the } at index 3?

Approach 1: Brute force

A natural first idea: a balanced string must contain at least one pair sitting side by side, like (), [] or {} (the innermost pair). Delete it. What’s left must still be balanced. Keep deleting adjacent pairs until nothing changes. If the string ends up empty, it was balanced.

"([]{})" → delete [] and {} → "()" → delete () → "". Valid!

Brute force: delete pairs until nothing changes

s = "([]{})"

s
  1. (0
  2. [1
  3. ]2
  4. {3
  5. }4
  6. )5
variables
pass
1
length
6
result
—
  • About to be deleted
  • Valid
  • Stuck: invalid

Pass 1: the string is "([]{})". We look for pairs that sit right next to each other, like "()", and delete them.

Step 1 / 8

Which line is running?

function isValid(s) {  let before = null;  // keep deleting matched pairs until nothing changesRunning now:   while (s !== before) {    before = s;    s = s.replaceAll("()", "");    s = s.replaceAll("[]", "");    s = s.replaceAll("{}", "");  }  return s.length === 0; // valid only if everything was deleted}

Brute force: delete pairs

function isValid(s) {  let before = null;  // keep deleting matched pairs until nothing changes  while (s !== before) {    before = s;    s = s.replaceAll("()", "");    s = s.replaceAll("[]", "");    s = s.replaceAll("{}", "");  }  return s.length === 0; // valid only if everything was deleted}
def is_valid(s):    before = None    # keep deleting matched pairs until nothing changes    while s != before:        before = s        s = s.replace("()", "")        s = s.replace("[]", "")        s = s.replace("{}", "")    return len(s) == 0  # valid only if everything was deleted

replaceAll("()", "") (JavaScript) and replace("()", "") (Python) build a new string with every "()" removed. before remembers the string from the start of the pass, so we can tell when a pass changed nothing.

Why is it slow?

Each pass reads the whole string, and one pass may only remove one layer of nesting. Take "((((()))))": 10 characters, 5 layers deep. Each pass removes only the innermost (), so it takes 5 passes (plus one to confirm), each reading up to 10 characters.

For a string of 10,000 characters nested 5,000 deep, that’s about 5,000 passes × 10,000 characters = 50,000,000 character reads, and each pass also builds brand-new strings. The work grows like n × n, which we write as O(n²): double the input, four times the work.

The pattern: stack for matching pairs

The brute force keeps re-reading the string to find the innermost pair. But we can know the innermost open bracket at every moment, in one left-to-right pass, if we keep the open brackets on a stack.

Pattern

Stack for matching pairs

Template

Use it when: things open and close, and each closer must match the most recent thing still open (brackets, HTML tags, undo steps).

Signal words

  • “valid parentheses”
  • “balanced”
  • “matching brackets”
  • “nested”
  • “remove adjacent pairs”

Approach 2: One pass with a stack

  1. Make a small lookup table pairs that says which opener each closer needs: ) needs (, ] needs [, } needs {.
  2. Make an empty stack.
  3. Read the string one character at a time.
  4. Opener? Push it. We can’t judge it yet; it waits for its closer.
  5. Closer? If the stack is empty, there is nothing to close: return false. Otherwise pop the top. If it isn’t the opener this closer needs, return false.
  6. After the loop, return true only if the stack is empty. Anything left was opened and never closed.

Press Play and watch the stack on the left grow and shrink. Each matched pair lights up green on the string. Then try the three failure examples: they show the three different ways a string can be invalid (wrong kind, nothing to close, and something left over).

Stack of openers

s = "([]{})"

s
  1. (0
  2. [1
  3. ]2
  4. {3
  5. }4
  6. )5
stackopeners waiting
  1. empty
variables
ch
—
needs
—
top (popped)
—
result
—
  • Reading now
  • Just pushed
  • Matched pair
  • Problem found
  • Already read

We read "([]{})" from left to right with an empty stack. The stack will hold every opener that is still waiting for its closer.

Step 1 / 11

Which line is running?

function isValid(s) {  const pairs = { ")": "(", "]": "[", "}": "{" }; // closer -> its openerRunning now:   const stack = [];  for (const ch of s) {    if (!(ch in pairs)) {      stack.push(ch); // an opener: remember it until its closer arrives      continue;    }    if (stack.length === 0) return false; // a closer with nothing to close    const top = stack.pop();    if (top !== pairs[ch]) return false; // the wrong kind of opener  }  return stack.length === 0; // leftovers were opened but never closed}

Notice that the stack always holds the openers in the order they’re still open. The top is always the innermost one, which is the only one a closer is allowed to close.

The code, line by line

One pass with a stack

function isValid(s) {  const pairs = { ")": "(", "]": "[", "}": "{" }; // closer -> its opener  const stack = [];  for (const ch of s) {    if (!(ch in pairs)) {      stack.push(ch); // an opener: remember it until its closer arrives      continue;    }    if (stack.length === 0) return false; // a closer with nothing to close    const top = stack.pop();    if (top !== pairs[ch]) return false; // the wrong kind of opener  }  return stack.length === 0; // leftovers were opened but never closed}
def is_valid(s):    pairs = {")": "(", "]": "[", "}": "{"}  # closer -> its opener    stack = []    for ch in s:        if ch not in pairs:            stack.append(ch)  # an opener: remember it until its closer arrives            continue        if not stack:            return False  # a closer with nothing to close        top = stack.pop()        if top != pairs[ch]:            return False  # the wrong kind of opener    return len(stack) == 0  # leftovers were opened but never closed

Most line numbers are the same in both languages. The two exceptions are the if ... return false checks: JavaScript fits each on one line (9 and 11), while Python uses two lines for each (8–9 and 11–12). JavaScript’s closing } braces keep everything else lined up.

  • Line 1: define the function. (On LeetCode it sits inside var isValid = function(s) in JavaScript, or class Solution with def isValid(self, s) in Python; the body is the same.)
  • Line 2: pairs is a hash map (a JavaScript object / a Python dict) from each closer to the opener it needs. Keying by the closer makes the check on line 11 a single lookup, and also gives us an easy “is this a closer?” test.
  • Line 3: an empty array (JS) or list (Python) that we use as a stack: push/append adds to the end, pop removes from the end. The end is the “top”.
  • Line 4: read the characters left to right.
  • Line 5: ch in pairs is true only for closers (the keys). So “not in pairs” means ch is an opener.
  • Line 6–7: push the opener and continue, which skips straight to the next character.
  • Line 9 (JS) / lines 8–9 (Py): a closer arrived but the stack is empty. Nothing is open, so this closer has nothing to close. Without this check, pop() on an empty stack would give undefined in JavaScript or crash with an error in Python.
  • Line 10: pop the most recent opener.
  • Line 11 (JS) / lines 11–12 (Py): if it isn’t the opener this closer needs (pairs[ch]), the brackets are crossed or the wrong kind. Stop right away.
  • Line 13: we read everything. Balanced only if nothing is still open.

Dry run

Trace s = "([]{})" by hand. Each row is one trip around the loop; the stack is written bottom → top.

ichopener or closer?what happensstack after
0(openerpush ((
1[openerpush [( [
2]closer, needs [pop [ → match(
3{openerpush {( {
4}closer, needs {pop { → match(
5)closer, needs (pop ( → match(empty)
endstack empty → return true(empty)
s = "([]{})"

The ] row (i = 2) is the important one: when ] arrives, the top of the stack is [, not (. The stack hands us exactly the opener we need to check, without searching.

Complexity

Brute force (delete pairs)

Time

O(n²)

Up to n/2 passes, each reading (and rebuilding) a string of up to n characters.

Space

O(n)

Each replace builds a new string of up to n characters.

One pass with a stack

Time

O(n)

We read each character once, and push/pop take one step each. 10,000 characters ≈ 10,000 steps.

Space

O(n)

In the worst case (all openers, like '(((((') every character sits on the stack.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Restate: “Each closer must match the most recent unclosed opener, and nothing can be left open.”
  2. Mention the naive idea: “I could keep deleting adjacent pairs, but that’s O(n²).”
  3. Name the pattern: “Most recent unclosed opener means last in, first out, so a stack.”
  4. List the three ways to fail: wrong kind, closer with an empty stack, leftovers at the end.
  5. Give the cost: O(n) time, O(n) space. Dry-run "([)]" to show it catches crossing.

Likely follow-up questions:

  • “Only round brackets?” Then a single counter works: +1 for (, −1 for ), never below 0, and 0 at the end. With several kinds, you need the stack.
  • “Return the index of the first error?” Return i instead of false inside the loop, and the index of the bottom leftover opener at the end (store indexes on the stack).
  • “Minimum brackets to add to make it valid?” Count closers with an empty stack plus leftovers.

Related problems:

  • Min Stack (this week): building a stack with an extra feature.
  • Evaluate Reverse Polish Notation (this week): a stack that holds values waiting for an operator, instead of openers waiting for a closer.
  • Generate Parentheses (LeetCode 22, a good extra): builds every valid string with backtracking.
  • The week 3 overview has the reusable template.