Valid Parentheses

Problem

Given a string s containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

A string is valid if:

1. Open brackets are closed by the same type of brackets.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Intuition

A stack is the natural data structure here. Push opening brackets onto the stack. When you encounter a closing bracket, check that the top of the stack is the matching opening bracket. If the stack is empty at the end, the string is valid.

Solution

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

Complexity

• Time: O(n) — single pass through the string
• Space: O(n) — stack stores at most n/2 opening brackets

Key Takeaway

Stacks are the go-to for matching/nesting problems. Whenever you need to match "most recent" opening with current closing, think stack.