Valid Parentheses | Stack Algorithm | Stack

Overview

Valid parentheses (or valid brackets) means checking whether a string of brackets—e.g. (), [], {}—is balanced: every opening bracket has a matching closing bracket in the correct order, and pairs are properly nested. A stack is the natural solution: push opening brackets; when you see a closing bracket, the most recent opening bracket (top of stack) must match it. If the stack is empty when you see a closer, or non-empty at the end, the string is invalid.

Why stack: The "last opened" bracket must close first (LIFO). The stack keeps exactly the set of currently open, unmatched brackets in order.

When to Use

Single type of brackets — e.g. only (); same logic, simpler match.
Multiple types — (), [], {}; push opening, on closing pop and check that the character matches (e.g. ( with )).
Minimum add/remove to make valid — Count unmatched open and close; or use the same stack and then derive edits.
Longest valid substring — Stack of indices; when you pop, you know the valid segment length. See Score of Parentheses for a variant.

How It Works

Map: Define which closing bracket matches which opening: e.g. ) → (, ] → [, } → {.
Scan: For each character:

If it's an opening bracket, push it onto the stack.
If it's a closing bracket: if the stack is empty, return false; else pop. If the popped character is not the matching opener, return false.

End: After the scan, return true only if the stack is empty (all opened brackets were closed).

Example 1: Valid Parentheses (Single Pass)

Problem: Given a string s containing only (, ), [, ], {, }, determine if the input is valid. Valid means: open brackets closed by the same type and in the correct order.

function isValid(s: string): boolean {
  const stack: string[] = [];
  const closeToOpen: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
  for (const c of s) {
    if (c in closeToOpen) {
      if (stack.length === 0 || stack.pop() !== closeToOpen[c]) return false;
    } else {
      stack.push(c);
    }
  }
  return stack.length === 0;
}

Time: O(n), Space: O(n).

Example 2: Only Round Brackets

If the string has only ( and ), you don't need a map; just push ( and on ) pop if non-empty, else invalid.

function isValidParens(s: string): boolean {
  let depth = 0;
  for (const c of s) {
    if (c === '(') depth++;
    else { if (depth === 0) return false; depth--; }
  }
  return depth === 0;
}

Space: O(1) (counter instead of stack when only one bracket type).

Example 3: Minimum Add to Make Valid

Problem: Return the minimum number of parentheses (either ( or )) you must add so the resulting string is valid.

Track balance: +1 for (, -1 for ). If balance goes negative, you need to add an opener (count it and treat balance as 0). At the end, add balance closers.

function minAddToMakeValid(s: string): number {
  let open = 0, add = 0;
  for (const c of s) {
    if (c === '(') open++;
    else { if (open === 0) add++; else open--; }
  }
  return add + open;
}

Edge Cases

Empty string — Valid; stack stays empty.
Only openers — Invalid; stack non-empty at end.
Only closers — Invalid; pop from empty (or balance goes negative).
Wrong nesting — e.g. ([)]; when you see ), top is [, mismatch → false.

Common Mistakes

Matching in wrong order — Always compare the popped character with the current closer; the stack gives you the most recent opener.
Forgetting final check — If the stack is not empty at the end, there are unclosed brackets; return false.
Assuming only one type — With multiple types, you must check that the popped opener matches the closer (e.g. [ with ) is invalid).

Time and Space Complexity

Time: O(n).
Space: O(n) for the stack; O(1) if only one bracket type and you use a counter.

Summary

Valid parentheses: Push openers; on closer pop and check match; valid iff stack empty at end.
Foundation for Score of Parentheses and expression parsing. See Stack Basics for the LIFO idea.