Valid Parentheses in Java

Valid Parentheses in Java

This guide explains the intuition, optimized approach, and Java implementation for valid parentheses in java, with practical tips for interviews and production coding standards.

Problem

Validate whether brackets in string are properly opened and closed in order.

Stack Approach

• Push expected closing bracket when opening bracket appears.
• On closing bracket, it must match top of stack.
• End with empty stack.

Java Solution

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

Complexity

• Time: O(n)
• Space: O(n)

Key Takeaways

• Start from the brute-force idea, then derive the optimized invariant.
• Use clean pointer/index boundaries to avoid off-by-one bugs.
• Validate against edge cases (empty input, single element, duplicates, extreme values).