Valid Parentheses Algorithm

Given a string containing (, ), {, }, [, ], determine if the parentheses are valid.

Valid means every opening bracket has a matching closing bracket, in the correct order. "([{}])" is valid. "([)]" is not.

The intuition

A stack is the natural fit here. Opening brackets get pushed. Closing brackets get matched against the top of the stack. If they match, pop. If they don't, the string is invalid.

Think of it like nesting. The most recently opened bracket must close first. That's exactly what a stack enforces — last in, first out.

The code

var isValid = function(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };

    for (const char of s) {
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        } else {
            if (stack.length === 0 || stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }

    return stack.length === 0;
};

How it works

Walk through each character. Opening bracket? Push it. Closing bracket? Pop the stack and check if it matches. If the stack is empty when you encounter a closer (nothing to match) or the popped bracket doesn't match, return false.

After processing every character, the stack should be empty. If it's not, there are unmatched opening brackets.

Complexity

• Time: O(n) — one pass through the string.
• Space: O(n) — the stack, in the worst case (all opening brackets).

Trade-offs

The stack solution is optimal. Some people try to use counters (count of open parens, brackets, braces), but that fails — "(]" would pass a counter-based check. You need order awareness, and a stack gives you that.