Steven JI

Posted on Mar 12

LeetCode 20. Valid Parentheses From Naive🤪 to Top Performant🔥 !

#java #leetcode

TL;DR: I'm a beginner, and I’ll show you my journey from a naive approach to a highly performant one. I've included step-by-step explanations for 3 different solutions. Hope it helps you!

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Solution 1 — Naive approach

class Solution {
    public static boolean isValid(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        List<Character> op = List.of('(', '{', '[');
        List<Character> ed = List.of(')', '}', ']');
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (op.contains(c)) {
                stack.addFirst(c);
            } else if (ed.contains(c)) {
                if (stack.isEmpty()) { return false; }
                Character top = stack.getFirst();
                if (top != op.get(ed.indexOf(c))) {
                    return false;
                } else {
                    stack.removeFirst();
                }
            }
        }
        return stack.isEmpty();
    }
}

Explanation:

Very simple, standard and intuitive solution, we use the Last-In-First-Out (LIFO) property of a Stack:

Traverse: Iterate through the string character by character.
Push: Store every opening parenthesis on a stack to remember the expected order of closing.
Match & Pop: For every closing parenthesis, verify two conditions:
- The stack is not empty (preventing underflow).
- The current character matches the type of the top element.

PS: It's been nearly a year I haven't programmed in Java, so even for the first solution I got stuck for 30mins on the syntax lol 🤣. I know this code is ~~trash~~ far from optimal, so bear with me! 🙏…

Performance Analysis:

Time Complexity: $O(n \cdot k)$ (effectively $O(n)$)
- For each of the $n$ characters, we perform op.contains(c) and ed.indexOf(c).
- Since the number of bracket types $k$ is small and constant ($k=3$), it's mathematically $O(n)$.
- The "Why": However, in practice, $n \times 3$ linear searches plus multiple method calls per iteration make the constant factor quite high.
Space Complexity: $O(n)$
- We use an ArrayDeque<Character> which, in the worst case, stores $n$ references.
- Memory Footprint: High. Each Character is a heap object. On a 64-bit JVM, the overhead of object headers makes this version consume significantly more RAM than raw data.
Leetcode Ranking::
- Runtime = 4ms (beats 42.05% 😭)
- Memory = 43.50 MB (beats 24.58%)

Drawbacks:

Autoboxing Overhead: Frequent conversion between primitive char and Character objects creates unnecessary heap pressure and slows down execution.
Hidden Linear Search: Using List.contains(c) and List.indexOf(c) inside a loop turns a simple check into a $O(k)$ operation. While $k$ is small (3), it adds significant constant-time overhead.
Memory Footprint: ArrayDeque<Character> stores object references rather than primitive values. In Java, a Character object consumes much more memory (up to 24 bytes) than a 2-byte primitive char.
Inefficient Mapping: The logic to match brackets via op.get(ed.indexOf(c)) is intellectually indirect and requires multiple method calls per character.
Redundant Object Allocation: Creating List.of(...) on every method call (if not static) allocates fresh objects on the heap that must be garbage collected.

Solution 2 — Logic Cleanup

class Solution {
    public boolean isValid(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(':
                    stack.push(')');
                    break;
                case '{':
                    stack.push('}');
                    break;
                case '[':
                    stack.push(']');
                    break;
                default:
                    if (stack.isEmpty() || stack.pop() != c) {
                        return false;
                    }
            }
        }
        return stack.isEmpty();
    }
}

Explanation:

I looked for a more advanced approach and stumbled upon this clever solution by phoenix13steve:

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}

It use a clever inverted check logic:

Instead of pushing the opening bracket and later mapping it to its partner, we push the expected closing bracket onto the stack.
This makes the comparison logic much cleaner: when we hit a closing bracket, we just check if it matches the one we popped.
It also uses the standard push() and pop() methods, which are more semantically appropriate for a stack than addFirst()/removeFirst().

Modern Adjustments:

Since that solution was posted in 2015, I made a few updates for 2026 standards:

Replaced Stack with ArrayDeque: Stack is a legacy class that uses synchronized methods, adding unnecessary overhead in single-threaded environments. It also incorrectly inherits from Vector.
Replaced toCharArray() with charAt(i): For memory efficiency, charAt(i) is preferred. toCharArray() creates a complete copy of the string, doubling the memory footprint for large inputs.
Used switch: For a small, fixed set of cases, a switch statement is highly optimized by the JVM.

Performance Analysis:

Time Complexity: $O(n)$
- The Improvement: We eliminated the $O(k)$ linear search (List.contains) from Solution 1.
- The "Why": The JVM compiles switch into a jump table (like tableswitch in bytecode). This reduces the character-matching logic to a near $O(1)$ branch. The "constant factor" is significantly lower than in Solution 1.
Space Complexity: $O(n)$
- Still $O(n)$ as we need to store up to $n$ characters in the worst-case scenario.
- Note: We are still using ArrayDeque<Character>, so we haven't solved the object-wrapping memory overhead yet.
Leetcode Ranking:
- Runtime = 3ms (beats 87.62% 😧)
- Memory = 43.15 MB (beats 84.20%)

Drawbacks:

Persistent Autoboxing: Even with better logic, we are still using ArrayDeque<Character>. Every char is automatically wrapped into a Character object. In high-performance scenarios, these object allocations create unnecessary pressure on the Garbage Collector.
Heap Overhead: Because we are storing Character objects rather than primitives, the memory footprint is still roughly 10x larger than it needs to be (due to Java object headers).
Missing Early Exit: The solution currently processes the entire string even if the length is odd (which is impossible for a valid sequence).
Method Call Overhead: While ArrayDeque is fast, it is still a complex collection. For a simple stack-based algorithm, we can achieve even higher performance by moving closer to the "metal."

Solution 3 - Stack Simulation

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 != 0) return false;

        char[] stack = new char[n];
        int top = -1;

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(' -> stack[++top] = ')';
                case '{' -> stack[++top] = '}';
                case '[' -> stack[++top] = ']';
                default -> {
                    if (top == -1 || stack[top--] != c) return false;
                }
            }
        }
        return top == -1;
    }
}

Explanation:

This version is all about Performance Engineering. I stripped away the Java Collections Framework entirely to talk directly to the memory.

Primitive Array as Stack: I replaced the ArrayDeque<Character> with a simple char[]. By doing this, I completely eliminated Autoboxing. We are now storing raw 2-byte char primitives instead of heavy Character objects.
Manual Pointer (top): Instead of calling methods like push() or pop(), I used a simple integer to track the stack's head. Incrementing and decrementing an integer is as fast as CPU operations get.
Early Pruning: I added a check for n % 2 != 0. If the string length is odd, it's impossible for every bracket to have a pair, so we can exit immediately without running the loop.
Enhanced Switch (Java 17+): Using the -> syntax makes the code cleaner and prevents "fall-through" bugs.

Performance Analysis:

Time Complexity: $O(n)$
- The Ultimate Optimization: While still linear, the constant factors are at their absolute minimum. There are zero method calls (except charAt) and zero object allocations inside the loop.
Space Complexity: $O(n)$
- Memory Footprint: Minimized. A char[] is the most memory-efficient way to store these characters. It uses roughly 10x less RAM than Version 1 or 2 because it avoids the overhead of object headers and internal collection nodes.
Leetcode Ranking:
- Runtime = 1ms (beats 99.78% 😎)
- Memory = 40.80 MB (beats 98.06%)

Trade-offs & Future Considerations

Readability vs. Performance: While Solution 3 is the fastest, it is lower-level. In a massive enterprise codebase where performance isn't the absolute bottleneck, Solution 2 might be preferred for its high readability and maintainability.
The HashMap Alternative: A common suggestion is to use a HashMap<Character, Character> to store bracket pairs.
- Pros: It makes the code extremely flexible (easy to add new bracket types like < > or « »).
- Cons: For this specific problem, it would re-introduce Object overhead and Hashing time, likely dropping the runtime back to 2–5ms. In high-performance Java, switch is almost always faster than a Map.
Safety over Speed: My array allocation new char[n] is safe but uses more memory than necessary (since the stack never exceeds n/2 in a valid string). In a memory-constrained system, new char[n / 2] would be a tighter optimization.
Robustness: This code assumes only the six bracket characters are present. If the input contained spaces or other characters, we would need to add a filter or a more robust default case in our switch.

What’s Next?

If you followed this journey from Solution 1 to Solution 3, you’ve seen that "solving a problem" is only the first step. The real growth happens when you start asking: "Can this be faster? Can this use less memory? Why is this tool slower than that one?"

If you want to practice these "Stack Simulation" skills, I recommend these next challenges:

155. Min Stack: Great for learning how to manage multiple states in a stack.
150. Evaluate Reverse Polish Notation: A perfect scenario to use the char[] and switch techniques we just mastered.
232. Implement Queue using Stacks: To deepen your understanding of LIFO vs. FIFO.
Or, Feel free to suggest further improvements! Can we squeeze even more performance out of this, or is this the limit for Java?

Final Thought: Don't be afraid to write "trash" code at first. Every 0ms solution started as a 3ms solution that someone refused to give up on. Keep iterating, keep asking "why," and happy coding! 🚀

DEV Community

LeetCode 20. Valid Parentheses From Naive🤪 to Top Performant🔥 !

Problem Statement

Solution 1 — Naive approach

Explanation:

Performance Analysis:

Drawbacks:

Solution 2 — Logic Cleanup

Explanation:

Performance Analysis:

Drawbacks:

Solution 3 - Stack Simulation

Explanation:

Performance Analysis:

Trade-offs & Future Considerations

What’s Next?

Top comments (0)