LeetCode 20 – Valid Parentheses

Valid Parentheses is the canonical "you should have reached for a stack" problem. Brackets nest, and nesting means the thing you must close next is always the thing you opened most recently — which is the definition of last-in, first-out. There is a small trick that makes the code shorter than most people write it.

The problem

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

"()"       -> true
"()[]{}"   -> true
"{[()]}"   -> true      properly nested
"(]"       -> false     wrong type
"([)]"     -> false     interleaved, not nested
"("        -> false     never closed
")("       -> false     closed before it was opened

"([)]" is the case that separates a real solution from a counter. Counting three pairs of matched brackets says this is fine. It is not — the ( has to close before the [ that was opened inside it can.

The idea, and the trick

Walk the string. Push every opening bracket. On a closing bracket, the top of the stack must be its partner — pop it and continue, or the string is invalid. At the end the stack must be empty; if it is not, something was opened and never closed.

The trick is what you push. The obvious version pushes the opener and then needs a helper that maps ( to ), [ to ], { to } at pop time. Instead, push the closer you expect to see. Then the check at a closing bracket is a single equality test against the popped character, and the mapping lives in one place.

"{[()]}"

{  push }        stack: }
[  push ]        stack: } ]
(  push )        stack: } ] )
)  pop ) == )    stack: } ]
]  pop ] == ]    stack: }
}  pop } == }    stack: empty  →  true

Three failure modes, three checks

All three have to be handled, and each is one condition:

• Wrong type — the popped expectation does not equal the character.
• Closing with nothing open — the stack is empty when a closer arrives, as in ")(". Popping an empty stack throws, so test before you pop.
• Opened and never closed — the stack is non-empty at the end, as in "(". Returning true the moment the loop ends is the bug here.

Java

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

        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> stack.push(')');   // push what must close it
                case '[' -> stack.push(']');
                case '{' -> stack.push('}');
                default  -> {
                    // Empty means this closer has nothing to close.
                    if (stack.isEmpty() || stack.pop() != c) return false;
                }
            }
        }

        return stack.isEmpty();   // anything left was never closed
    }
}

Use ArrayDeque, not Stack. java.util.Stack extends Vector, so every operation is synchronised for a lock nobody wants, and it iterates bottom-to-top — the opposite of the order a stack implies. Its own Javadoc points at Deque instead. Reaching for it is a small tell, and reaching for ArrayDeque is a small win.

An early if (s.length() % 2 != 0) return false; is a legitimate fast path — an odd number of characters can never balance. It changes no answers, so treat it as an optimisation to mention rather than a rule the solution depends on.

Python

class Solution:
    CLOSER = {"(": ")", "[": "]", "{": "}"}

    def isValid(self, s: str) -> bool:
        stack = []

        for c in s:
            if c in self.CLOSER:
                stack.append(self.CLOSER[c])     # push what must close it
            elif not stack or stack.pop() != c:
                return False

        return not stack

A plain list is the right stack in Python — append and argument-less pop are both amortised O(1) at the end. collections.deque is for when you also need to pop from the front.

Complexity

O(n) time — each character is pushed at most once and popped at most once. O(n) space for the stack, which is unavoidable: "((((((..." genuinely has to remember every unclosed bracket, and there is no constant-space solution. If the input were a single bracket type, a counter would do it in O(1) — the stack exists purely to remember which type.

What this generalises to

The same push/pop skeleton with a different payload solves a whole family: Min Stack (155), Evaluate Reverse Polish Notation (150), Basic Calculator (224), Remove All Adjacent Duplicates (1047), and Longest Valid Parentheses (32), which pushes indices so it can measure the span of each valid run. Recognising "the most recent unresolved thing" in a problem statement is the signal.

What the interviewer is checking

• That you reach for a stack immediately, and can say why counting fails on "([)]".
• That you check for an empty stack before popping — ")(" is the test.
• That the stack must be empty at the end, not merely never mismatched.
• That an empty string returns true.
• ArrayDeque over the legacy Stack, if you are writing Java.