Patterns / Valid Parentheses walkthrough

Valid Parentheses — A Worked Walkthrough

Why a stack is the right model, with the full solution and a dry run.

The problem

Given a string containing the brackets (), [], and {}, decide whether it is valid. A string is valid when every opening bracket is closed by the matching type, and brackets close in the correct order — so ([]) is valid but ([)] is not.

Why a stack

The crucial observation is "correct order": the most recently opened bracket must be the first one closed. That is exactly last-in-first-out behavior, which is what a stack provides. Push every opening bracket; when you meet a closing bracket, the top of the stack must be its match.

The solution

Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
        stack.push(c);
    } else {
        // closing bracket: stack top must be its match
        if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
    }
}
return stack.isEmpty(); // nothing left unclosed

O(n) time and O(n) space — each character is pushed or popped at most once.

A quick dry run

Take s = "([])":

1. '(' → push. Stack: [ (
2. '[' → push. Stack: [ ( [
3. ']' → pop '[', matches pairs[']'] → ok. Stack: [ (
4. ')' → pop '(', matches pairs[')'] → ok. Stack empty.
5. End: stack is empty → valid.

Edge cases to mention

• A closing bracket with an empty stack, e.g. ")" → invalid (nothing to match).
• Leftover openers at the end, e.g. "(" → invalid (must end empty).
• Mismatched types, e.g. "(]" → invalid.
• Empty string → conventionally valid.

The takeaway

This is the textbook stack problem: whenever ordering and "most recent unmatched thing" drive the logic, reach for a stack. The same model powers expression evaluation, the min-stack, and decoding nested strings. Practice it here.