Valid Parentheses Problem — Explained with Java Optimizations

✅ Valid Parentheses Problem — Explained with Java Optimizations

The Valid Parentheses problem is a classic question asked in coding interviews and on platforms like LeetCode. The goal is to determine whether a given string containing only brackets (()[]{}) is well-formed, meaning every opening bracket has a matching closing bracket in the correct order.

---

📌 Problem Statement

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

A string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

✅ Examples:

Input	Output	Explanation
"()"	true	Correctly paired
"()[]{}"	true	All types correctly paired
"(]"	false	[ is not closed by ] properly
"([)]"	false	Incorrect nesting
"{[]}"	true	Properly nested and matched

---

🧠 Intuition

We need to:

1. Track opening brackets.
2. For every closing bracket, check if it matches the last opened bracket.
3. If anything mismatches or remains unmatched at the end, the string is invalid.

This is a perfect use case for a stack — Last-In-First-Out (LIFO) structure.

---

💡 Optimal Stack-Based Java Solution

import java.util.Deque;
import java.util.ArrayDeque;

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

        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();
    }
}

✅ Time & Space Complexity

Aspect	Complexity
Time	O(n)
Space	O(n)

We scan the string once and use a stack that can hold up to n characters.

---

🔥 Ultra-Optimized Java (No Boxing, Fastest)

If you're aiming for 0ms on LeetCode and avoiding Java collection overhead, use a raw array:

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = -1;

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack[++top] = c;
            } else {
                if (top == -1) return false;
                char open = stack[top--];
                if ((c == ')' && open != '(') ||
                    (c == '}' && open != '{') ||
                    (c == ']' && open != '[')) {
                    return false;
                }
            }
        }

        return top == -1;
    }
}

🚀 Why this is faster:

• No Character object boxing/unboxing.
• No Deque or method call overhead.
• Tight loop with primitive types.

---

🤔 Why Some Submissions Show 0ms?

You're not alone if you wonder: Why does someone get 0ms and I get 2ms?

It's due to:

• Execution environment randomness.
• JVM warm-up time.
• Input size/load on LeetCode server.
• Java timer granularity (below ~1ms rounds to 0ms).

So don’t worry — your algorithm is already optimal.

---

🧪 Test Cases to Try

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
System.out.println(isValid(""));            // true (empty is valid)
System.out.println(isValid("((((("));       // false

---

📚 Conclusion

• Use a stack to track brackets.
• Optimize with ArrayDeque or char[] based on performance needs.
• You can’t do better than O(n) — that’s the lower bound for reading all characters.

✅ If you're using the array-based method above, you're already at peak efficiency.

---

🔁 Related Posts

If you enjoyed this post, you might also find these helpful:

• How to Use AI Tools for Novel Writing: Worldbuilding, Characters, and Plots
• Creating Stunning Business Presentations in Under 10 Minutes with AI Tools like Tome or Gamma
• Top 5 AI-Powered Interior Design Tools to Visualize Room Layouts and Color Schemes
• GitHub Copilot vs. Tabnine vs. Claude AI: A Comprehensive Code Assistant Comparison

---

🚀 Explore More & Work With Us

🔧 Try Our Free Tools

We believe in empowering creators and developers. Here are some completely free tools we've built that might help you:

• Meme Generator – Create and customize memes with our easy-to-use tool.
• QR Code Generator – Generate custom QR codes for websites, contact info, and more.
• Markdown to HTML Previewer – Live preview your markdown as responsive HTML.

More tools coming soon on GILASA GROUP

💼 Hire Us for Custom Software Development

Whether you're looking to build a custom website, AI tool, or full-fledged SaaS product, our expert team is here to help.

👉 Work With Us – Let’s build something amazing together!