20. Valid Parentheses

Given a string of ()[]{} characters, decide whether every bracket is closed by the same type of bracket, in the right order.

Stack matching (LIFO): the most recently opened bracket must close first.

Push openers onto a stack; on a closer, check the stack isn't empty, then compare against Map<closer, matching-opener> — pop on match, return false on mismatch or empty stack; after the loop, valid only if stack is empty.

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> parentheses = new HashMap<>();
        Deque<Character> stack = new ArrayDeque<>();

        parentheses.put(')', '(');
        parentheses.put('}', '{');
        parentheses.put(']', '[');

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (parentheses.get(c).equals(stack.peek())) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

1. Typo, wouldn't compile: wrote pathenteses.get(c) instead of parentheses.get(c) — mismatched variable name. Compiler error (cannot find symbol), not a logic bug. Reminder: this is why you always compile-check before you're "done," typos hide easily in your own code.
2. Used == instead of .equals() on boxed Character objects: parentheses.get(c) == stack.peek(). Map.get() and Deque.peek() both return Character objects (autoboxed), so == compares references, not values. This happened to work only because Character caches ALL values 0–127 (full ASCII range) per the JLS — so it was accidentally correct, not correctly reasoned. Would silently break with a type where the cache range is smaller (e.g. Integer, cached only -128 to 127).

Concept to re-drill

Autoboxed object comparison (== vs .equals()) — I know the rule in theory but still reached for == under pressure while focused on the stack logic. This is the single most important trap to build instinct against, since it produces code that looks correct and runs correct on small test cases, which makes it dangerous.

What I got right without help

• Push/pop stack mechanics
• Empty-stack guard BEFORE peeking (this is the defensive-indexing habit from Ch.6)
• Correct final check (stack.isEmpty()) to catch unclosed openers
• Chose ArrayDeque over legacy Stack correctly

Interview-ready: Mostly yes — the algorithm was right on the first pass. The ==/.equals() slip is the thing to actively watch for next time, not the pattern itself.

• Time: O(n) — one pass over the string.
• Space: O(n) — the stack, when every character is an opener.

• Can I write it from memory without looking?
• Why does == on two Character values from a Map and a Deque happen to work here, and when would it break?