Balanced Parentheses

The balanced-parentheses problem is the canonical stack exercise; a Map of bracket pairs and a single pass over the string solves it in linear time.

4 min read Level 2/5 #dsa#stack#balanced-parens

What you'll learn

Implement the balanced-parentheses check using a stack and a Map
Explain why the stack guarantees correct nesting order
Extend the solution to handle edge cases like empty strings and odd lengths

Given a string containing only (, ), {, }, [, and ], determine whether every opening bracket has a corresponding closing bracket in the correct order. This is one of the most common warm-up problems in technical interviews, and a stack makes it trivial.

The Algorithm

Walk the string one character at a time:

If the character is an opener ((, {, [), push it onto the stack.
If the character is a closer (), }, ]), pop the stack and check that the popped opener matches.
If the stack is empty when you try to pop, or the popped opener does not match, return false.
After the loop, return true only if the stack is empty (no unmatched openers left).

function isValid(s) {
  if (s.length % 2 !== 0) return false; // odd length can never balance

  const pairs = new Map([
    [")", "("],
    ["}", "{"],
    ["]", "["],
  ]);

  const stack = [];

  for (const ch of s) {
    if (pairs.has(ch)) {
      // closer: top of stack must be the matching opener
      if (stack.pop() !== pairs.get(ch)) return false;
    } else {
      // opener: push onto stack
      stack.push(ch);
    }
  }

  return stack.length === 0;
}

console.log(isValid("()[]{}"));   // true
console.log(isValid("([{}])"));   // true
console.log(isValid("(]"));       // false
console.log(isValid("([)"));      // false
console.log(isValid(""));         // true

Why the Stack Works

The stack preserves nesting order. The most recently seen unmatched opener is always on top, which is exactly what you need when the next closer arrives. Using any other structure — an array indexed from the front, a counter, a set — loses this ordering information.

Complexity

Metric	Value
Time	O(n)
Space	O(n)

In the worst case (all openers, no closers) the entire string is pushed onto the stack, giving O(n) space.

Common Variations

Minimum removals to make valid — count unmatched openers after the loop and unmatched closers during the loop; the answer is their sum.

Score of parentheses — replace the boolean with a numeric accumulator that increases or decreases based on depth.

Longest valid substring — store indices on the stack instead of characters so you can compute span lengths.

All three share the same single-pass, push-on-open, pop-on-close skeleton.

Up Next

The monotonic stack extends this idea to problems where you need to track the nearest element that is greater or smaller than the current one.

Monotonic Stack →