20. Valid Parentheses

If you’ve ever stared at a compiler error that just says “expected },” you already have the intuition for this one. Matching brackets is the textbook reason a stack exists, and Valid Parentheses is where that click happens. It’s the entry point to the stack pattern — get the last-in-first-out idea here and a lot of parsing problems stop looking scary.

The problem

You get a string made only of the six bracket characters ()[]{}. Return true if every opener is closed by the matching closer and in the right nested order, false otherwise. (Full statement on LeetCode.)

So "()[]{}" is valid, "{[]}" is valid, but "(]" and "([)]" are not — the second one interleaves brackets instead of nesting them.

Intuition: the most recent opener is all that matters

The rule that makes this a stack problem is ordering. When you hit a closer, it doesn’t have to match just any open bracket still waiting — it has to match the most recent one you haven’t closed yet. That “most recent, not yet resolved” phrasing is a stack described in plain English: last in, first out.

Walk "{[]}" by hand. Push {, push [. Now you see ] — peek the top, it’s [, they pair, pop it. Next is } — top is {, they pair, pop it. Stack is empty, so the string is balanced. Now try "([)]": push (, push [, then ) arrives and the top is [, not (. Mismatch, bail immediately. The stack catches the interleaving that a plain counter never could.

Two failure modes fall out of this naturally. A closer with nothing on the stack means there’s no opener to match — invalid. And leftover items on the stack at the end mean some openers were never closed — also invalid. A valid string leaves the stack exactly empty.

Solution

Push openers; on each closer, pop and check the pair. I map each closer to the opener it expects, which keeps the loop body flat instead of a stack of if branches.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

class Solution {
    public boolean isValid(String s) {
        // closer -> the opener it must match
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                // c is a closer: it must sit on top of its matching opener
                char opener = pairs.get(c);
                if (stack.isEmpty() || stack.pop() != opener) {
                    return false;
                }
            } else {
                // c is an opener: remember it for later
                stack.push(c);
            }
        }
        // anything left over is an unclosed opener
        return stack.isEmpty();
    }
}

A note on ArrayDeque over the older Stack class: Stack extends Vector and synchronizes every method, which you don’t need here. ArrayDeque is the modern choice for a LIFO stack and it’s the one to reach for in an interview.

Complexity

Metric	Value
Time	$O(n)$
Space	$O(n)$

One pass over the string is $O(n)$. Space is $O(n)$ because a string like "(((((" pushes every character before it ever pops one.

In an interview

Say the key sentence out loud before you code: “a closer has to match the most recent unmatched opener, which is exactly a stack.” That one line shows you picked the structure for a reason instead of pattern-matching on the title.

The bug that bites people is forgetting the empty-stack check. If you pop before confirming the stack has something in it, ")" throws instead of returning false — and interviewers reach for that input first. The other trap is returning true the moment the loop ends; you still have to verify the stack is empty, or "(((" sneaks through. Worth clarifying up front too: the constraints promise bracket-only input, so ask whether stray characters are possible before you assume they aren’t.

Once the stack clicks here, the same “remember the most recent thing, resolve it later” shape carries into harder problems — expression evaluation, the min-stack, and monotonic-stack questions all lean on it. The stack pattern hub lays out where it recurs.

References

• LeetCode 20 — Valid Parentheses