Valid Parentheses in Java: Why a Stack Is the Right Tool for the Job

Valid Parentheses looks like a simple string problem, right up until you try to solve it without a Stack and end up rebuilding one badly by hand. It's one of the most asked interview questions for a reason — it's a two-minute check on whether you actually understand Last In, First Out, or whether you're improvising something that only happens to work on the examples in front of you.

What the problem is actually asking

Valid Parentheses shows up in interviews so often that it's easy to treat it as a formality — something to clear quickly on the way to a "real" question. That's a mistake. It's a two-minute check on whether you actually reach for a Stack when the problem calls for one, or whether you improvise something that happens to work on the examples in front of you.

The problem, stated plainly: you're given a string made only of these six characters — ( ) { } [ ] — and you need to decide whether it's valid. A string is valid when every opening bracket has a matching closing bracket, the brackets close in the correct order, and every closing bracket matches the most recent bracket that hasn't been closed yet.

"()"       → true
"()[]{}"   → true
"(]"       → false
"([)]"     → false
"{[]}"     → true

The two false cases are the ones worth sitting with. (] fails because the bracket types don't match. ([)] is more interesting — every bracket has a partner somewhere in the string, but they close in the wrong order. That second case is the whole problem in miniature.

The mental model: doors that have to close in the order they opened

Think of each opening bracket as a door you've just opened. The rule is simple: whichever door you opened most recently has to be the next one you close. You can open as many doors as you like, but you can't reach past an open door to close one further back.

Open (
Open [
Close ]   ← closes the most recently opened door, [
Close )   ← now closes (, the only door left open

Everything matches. Valid.

Now watch what happens when the order breaks:

Open (
Open [
Close )   ← the most recently opened door is [, not (

Invalid — you tried to close a door that wasn't next in line.

"Whichever opened last has to close first" is exactly the definition of a Stack — Last In, First Out. That's not a coincidence you need to spot cleverly; it's the problem telling you which data structure to use, if you know how to listen for it.

Turning the mental model into an algorithm

Once you've recognised the LIFO pattern, the algorithm mostly writes itself:

Step 1. Walk through the string one character at a time. Every time you see an opening bracket — (, [, or { — push it onto the stack.

Step 2. Every time you see a closing bracket, look at whatever's currently on top of the stack. If it's the matching opening bracket, pop it off and move on. If it isn't — or if the stack is empty when you expected something to be there — the string is invalid, and you can stop immediately.

Step 3. After you've processed every character, check the stack one last time. If it's empty, every bracket found its partner and the string is valid. If anything is still sitting on the stack, there's an opening bracket that was never closed, and the string is invalid.

That third step is the one people forget. A string like "(((" never triggers a mismatch while you're reading it — there's simply nothing left to close it. Skip the final emptiness check and you'll happily mark that string valid, which it isn't.

Walking through an example

Take "{[()]}" and follow the stack one character at a time.

Stack is empty at the end, so the string is valid.

Now compare it against the invalid case, "([)]":

The moment the top of the stack doesn't match, you're done. There's no need to keep scanning the rest of the string.

Java code

import java.util.Stack;

public class ValidParentheses {

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if (ch == ')' && top != '(') return false;
                if (ch == '}' && top != '{') return false;
                if (ch == ']' && top != '[') return false;
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("()"));       // true
        System.out.println(isValid("()[]{}"));   // true
        System.out.println(isValid("(]"));        // false
        System.out.println(isValid("([)]"));      // false
        System.out.println(isValid("{[]}"));      // true
    }
}

Every line in that loop maps directly back to one of the three steps above: push on an opener, pop-and-compare on a closer, and the final stack.isEmpty() catches anything left dangling.

Saying it out loud in an interview

If an interviewer asks you to talk through your approach, this is the shape of a clean answer:

"I used a Stack because brackets have to close in the reverse order they opened — that's a Last In, First Out relationship. Whenever I see an opening bracket, I push it. Whenever I see a closing bracket, I check whether the stack is empty first, since popping an empty stack would throw an exception. If it's not empty, I pop the top element and check that it matches the closing bracket I'm looking at. Any mismatch, and I return false right away. If I make it through the whole string, I return whether the stack is empty — because an empty stack means every opening bracket found its match, and anything left over means something was never closed."

That answer covers the data structure choice, the two failure conditions, and the final check — the three things an interviewer is actually listening for.

Mistakes that quietly break this problem

Time and space complexity

The algorithm runs in O(n) time — every character in the string is visited exactly once, and each push, pop, or peek on the stack is O(1). Space is O(n) in the worst case, which happens when the string is nothing but opening brackets, like "((((((((". In that scenario every character gets pushed and nothing ever gets popped, so the stack grows as large as the input itself.

Why this problem keeps coming up

Valid Parentheses isn't really about brackets. It's a small, contained test of whether you recognise a Last In, First Out relationship when you see one, and whether you reach for the data structure built for exactly that — instead of trying to fake it with counters or extra loops that happen to pass the visible test cases. Once that recognition clicks, a whole family of other problems gets easier: matching HTML or XML tags, checking whether a compiler's syntax is balanced, validating nested expressions, undo/redo stacks in editors. All of them are the same shape wearing a different costume.