Valid Parentheses

Problem

Given a string s containing only the characters '(', ')', '{', '}', '[', ']', determine whether the input is balanced.

A string is balanced if every opening bracket is closed by the same type of bracket, and in the correct order.

Intuition

Brackets obey a last-in, first-out rule: the most recently opened bracket must be the first one closed. That's the exact semantics of a stack.

Push every opener. When you see a closer, pop the top and check it matches. If the stack is empty on a closer — or nonempty at the end — the string is unbalanced.

This generalizes to any nesting problem: function call frames, JSON parsing, HTML tag matching. Stack is the canonical "what's the most recent unresolved thing?" data structure.

Approach

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<u8> = Vec::with_capacity(s.len());

        for &c in s.as_bytes() {
            match c {
                b'(' | b'[' | b'{' => stack.push(c),
                b')' => if stack.pop() != Some(b'(') { return false; },
                b']' => if stack.pop() != Some(b'[') { return false; },
                b'}' => if stack.pop() != Some(b'{') { return false; },
                _ => return false,
            }
        }

        stack.is_empty()
    }
}

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

  for (const c of s) {
    if (c === "(" || c === "[" || c === "{") {
      stack.push(c);
    } else if (match[c] !== undefined) {
      if (stack.pop() !== match[c]) return false;
    } else {
      return false;
    }
  }

  return stack.length === 0;
}

Trace

Input: "([])"

Final: stack empty → true.

Edge cases

• Empty string — trivially balanced; returns true.
• Odd length — guaranteed unbalanced; micro-opt is a short-circuit s.length % 2 !== 0.
• Closer with empty stack — handled by the "pop returns None/undefined ≠ opener" check.
• Leftover openers — caught by the final is_empty() / length === 0 check.

Takeaway

When order-of-operations matters and the relationship is last-opened-first-closed, reach for a stack. Scales from this one-screen problem all the way up to compilers and runtime systems.