20. Valid Parentheses

id: 20 title: Valid Parentheses tags:

• stack

# Question

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

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

# Solution

# Pattern

Stack (LIFO) Use a Last-In-First-Out (LIFO) data structure. The most recently opened bracket must be the first one to be closed.

# How to Identify

• The problem involves matching pairs of items.
• Items are strictly nested (e.g., Russian nesting dolls, HTML tags, AST parsing).
• The phrase "validity of sequence" or "balanced sequence" is used.

# Description

Step-by-step explanation:

1. Early Exit: Check if the length of the string is odd. If it is, it's mathematically impossible for it to be balanced. Return false.
2. Iterate: Go through each character in the string one by one.
3. Push Expected: When encountering an opening bracket ((, {, [), do not push the opening bracket itself. Instead, push the closing bracket to the stack. This acts as a "promise" of what we expect to see later.
4. Validate Closing: When encountering a closing bracket, check two things:
   • Is the stack empty? (This means we have a closing bracket with no opening bracket).
   • Does popping the top of the stack equal the current character? (If not, a mismatch occurred).
   • If either is true, return false.
5. Final Check: After the loop, the stack must be empty. If it isn't, there were unclosed opening brackets left over.

# The Intuition

Think of this like an undo stack in a text editor or Russian nesting dolls. You can only close the doll you most recently opened. By pushing the "expected" closing half to a stack, you are constantly checking if the current piece of the string matches your most immediate, pending expectation.

# Complexity

# Time Complexity

We iterate through the string of length $N$ exactly once. Stack push() and pop() operations execute in $O(1)$ constant time. Thus, the total time complexity is $O(N)$.

# Space Complexity

In the worst-case scenario (e.g., "(((((((("), we will push $N$ characters onto the stack. Thus, auxiliary space scales linearly with $O(N)$.

# Code

class Solution {
    public boolean isValid(String s) {
        if (s.length() % 2 != 0) return false;
 
        Deque<Character> stack = new ArrayDeque<>();
 
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
 
            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();
    }
}

# Caveats

• Legacy Classes: Using java.util.Stack implies thread-safety lock contention on every operation. Modern Java strictly prefers ArrayDeque for stack simulations.
• toCharArray() Overhead: s.toCharArray() creates a distinct $O(N)$ memory clone of the string's backing array. Use s.charAt(i) to maintain true optimal memory footprint.

# Concepts to Think About

• Mapping for Scalability: If the problem allowed for 50 different types of brackets (e.g., custom parsers), using if-else chains becomes unmaintainable. The scalable approach is to populate a HashMap<Character, Character> with the pairings map.put('(', ')') and use the map for lookups.
• Constant Space Optimization: Can this be done in $O(1)$ space? Generally, no. A string can have a deeply nested sequence (((((...)))) which requires memory proportional to the nesting depth.
• Primitive Array Stack: For absolute maximum performance (often seen in competitive programming), you can simulate the stack using a primitive char[] stack = new char[s.length()] and an integer pointer int head = -1;. This avoids Object allocation entirely.

# Logical Follow-up

Question: How would you extend this to ignore all non-bracket alphanumeric characters in the string, for instance parsing "{ a + [ b * (c - d) ] }"? Solution: The structure remains entirely identical. You simply add a preliminary check if (c != '(' && c != ')' ...) to continue (skip) to the next character in the loop. The odd-length early exit constraint must be removed, as the string length no longer guarantees parity of the brackets.