4.8.1 — Valid Parentheses

LeetCode 20 · Easy · ★ Blind 75

The problem

A string contains only ()[]{}. Return true if every bracket is closed by the matching type, in the right order.

"()[]{}"   →  true
"(]"       →  false
"([)]"     →  false    (correct types, wrong order)
"{[]}"     →  true

The pattern

"([)]" is the example that tells you what structure to use. Counting brackets is not enough — you need to know which bracket is still waiting to be closed, and the answer is always the most recent one.

Most recent first is last-in-first-out, which is a stack.

Push every opening bracket. On a closing bracket, whatever is on top of the stack must be its partner. If it is not, the string is invalid.

The solution

Python

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []

        for c in s:
            if c in pairs:                      # a closing bracket
                if not stack or stack.pop() != pairs[c]:
                    return False
            else:                               # an opening bracket
                stack.append(c)

        return not stack                        # nothing left unclosed

TypeScript

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  const stack: string[] = [];

  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false;
    } else {
      stack.push(c);
    }
  }

  return stack.length === 0;
}

The map is keyed by the closing bracket, which is the direction you look things up in. When you see ), you want to know what should be underneath it.

Three checks, and all three are needed:

• Stack empty on a closing bracket — a closer with nothing to close, as in ")". In Python stack.pop() on an empty list raises, so the not stack guard comes first. In JavaScript pop() on an empty array returns undefined, which will never equal a bracket, so the comparison catches it on its own.
• Wrong type on top — "(]".
• Stack not empty at the end — openers that were never closed, as in "(((".

Forgetting the last one is the usual bug, and it passes most small test cases.

Trace

s = "{[]}"

char	action	stack
{	push	{
[	push	{ [
]	pop [, matches	{
}	pop {, matches	empty

Empty at the end → true.

Complexity

O(n) time, O(n) space — the worst case is a string of all openers.

Why this problem matters more than it looks

Nesting is everywhere, and everywhere it appears the answer is a stack:

• Parsing — HTML tags, JSON braces, and every programming language's block structure. A compiler's parser is doing exactly this with a much bigger alphabet. Chapter 3.2.
• The call stack — a function call is an opener and a return is a closer. That is why recursion works, and why a missing return is a leak. Chapter 2.2.
• Undo history — the most recent action is the first to undo.

If you can see nesting in a problem, you have already chosen the data structure.

Where this goes next

• Longest Valid Parentheses (LeetCode 32) — the longest balanced stretch. A stack of indices, with a sentinel index at the bottom to measure lengths against.
• Remove Invalid Parentheses, Minimum Add to Make Parentheses Valid — counting versions where you do not need the stack, only two counters, because there is a single bracket type.
• Generate Parentheses — building all valid strings rather than checking one. That is 4.8.4, and it is backtracking rather than stacking.

Next: 4.8.2 Min Stack — a stack that also answers "what is the smallest value in here" instantly.