LeetCode 20: Valid Parentheses – Java Stack Solution Explained

Meta Description: Learn how to solve LeetCode Problem 20, “Valid Parentheses,” using a stack-based approach. Step-by-step Java solution with detailed explanation and complexity analysis. Great for coding interviews and DSA prep.

🧠 Problem Statement

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

A valid string must:

1. Contain matching pairs of brackets.
2. Ensure brackets close in the correct order (Last-In-First-Out).

✅ Example

Input: s = "()[]{}"
Output: true
Explanation: All brackets are correctly matched and closed.

🧰 Why Use a Stack?

A stack is the ideal data structure for this problem because of its LIFO (Last-In-First-Out) nature. The last opening bracket must be the first to be closed, which is exactly what a stack handles best.

🔍 Benefits:

• Linear time: One pass through the string.
• Efficient memory: Uses space only for unmatched opening brackets.

🔍 Step-by-Step Approach

🖥💻 Algorithm:

1. Initialize an empty stack to hold opening brackets.
2. Traverse the string one character at a time:
   • If it’s an opening bracket, push it onto the stack.
   • If it’s a closing bracket, check if it matches the top of the stack.
     • If not, return false.
3. Final check: If the stack is empty, all brackets matched correctly.

💻 Java Code Solution

import java.util.Stack;

class Solution {
    public 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 != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

📘 Code Breakdown

🔐 Stack Initialization

• A Stack<Character> is used to hold all opening brackets.

➕ When We See an Opening Bracket

• Push it onto the stack: (, [, or {.

➖ When We See a Closing Bracket

• Check for underflow: If the stack is empty, return false.
• Pop and match: Ensure the popped character is the correct opening bracket.
  • If not, it’s an invalid sequence.

✅ Final Stack Check

• After traversing the string, the stack should be empty. If not, some brackets weren’t closed.

📊 Time and Space Complexity

🧠 Visual Walkthrough

✔ Valid Input: "([{}])"

1. Push ( → stack: [ ( ]
2. Push [ → stack: [ (, [ ]
3. Push { → stack: [ (, [, { ]
4. Match } → pop {
5. Match ] → pop [
6. Match ) → pop (
7. Stack is empty → return true

❌ Invalid Input: "([)]"

1. Push (, then [
2. Encounter ) → stack top is [, not matching → return false

⚠️ Common Mistakes to Avoid

1. Not checking for empty stack before popping.
2. Mismatch errors – like matching } with [.
3. Forgetting the final stack check – leftover elements mean unclosed brackets.

🏁 Conclusion

Using a stack is the cleanest and most efficient way to validate parentheses. It reflects the natural nesting structure of brackets and ensures your code remains readable and performant—perfect for coding interviews and real-world scenarios.

🔁 Related Problems to Practice

• 🔗 Generate Parentheses (LeetCode 22)
• 🔗 Minimum Add to Make Parentheses Valid (LeetCode 921)
• 🔗 Longest Valid Parentheses (LeetCode 32)

Need help understanding a concept? Drop your question in the comments! 💬

Keywords: valid parentheses leetcode, stack matching brackets, java parentheses validation, leetcode 20 explained, stack data structure, java stack example, bracket validation java, leetcode stack problems, coding interview stack problem, balanced parentheses java.