Valid Parentheses Algorithm Solution

The valid parentheses problem requires checking if a string containing only parentheses characters is properly balanced and nested. This classic algorithmic challenge demonstrates fundamental stack usage for matching opening and closing brackets in correct order.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input string contain characters other than parentheses, or only '(', ')', '{', '}', '[', ']'?
2. What is the expected time complexity constraint? Should we aim for O(n) or better?
3. Are we allowed to modify the input string, or must we work with a copy?
4. How should we handle invalid inputs like null or empty strings?
5. Should we return true/false for valid/invalid parentheses, or handle other error conditions?

Restated problem:
Given a string containing only the characters '(', ')', '{', '}', '[', and ']', determine if the input string has valid matching parentheses. Valid parentheses must be properly nested and closed in the correct order.

Input/Output specifications:

• Input: A string of length 0 to 10⁴ containing only parentheses characters
• Output: Boolean value indicating whether the parentheses are valid

Constraints and assumptions:

• The string will only contain the six characters: '(', ')', '{', '}', '[', ']'
• The string can be empty (which is considered valid)
• We need to check both proper nesting and matching of opening and closing brackets
• The solution should handle all valid combinations like "()", "{}[]", or "{[()]}" but reject invalid ones like "(]", "([)]", or "((("

Data shape and structure:
This is a linear sequence of characters with an implicit stack-like structure where we need to match opening brackets with their corresponding closing brackets in LIFO (Last In, First Out) order.

Core insight:
The problem requires maintaining a stack of unmatched opening brackets and ensuring that each closing bracket matches the most recently opened bracket, making it a classic stack-based validation problem.

2. Pattern Recognition

The problem exhibits the stack pattern for matching nested structures.

The key signals are:

• Balanced nesting requirements: Each opening bracket must have a corresponding closing bracket in the correct order
• Last-In-First-Out (LIFO) behavior: The most recently opened bracket must be the first one to close
• Sequential processing with dependency: We need to track what brackets are currently "open" and ensure proper closure

This is a classic stack problem because:

1. We're dealing with nested structures that require LIFO processing
2. Each closing bracket must match the most recently opened bracket of the same type
3. The problem naturally maps to a "push when opening, pop when closing" pattern

The core insight is that we can use a stack to maintain the set of currently open brackets, and each closing bracket must match the most recently added bracket from the stack.

This pattern appears in many variants:

• Valid parentheses matching
• Expression parsing and evaluation
• Nested structure validation (HTML/XML tags, function calls)
• Balanced bracket problems with multiple bracket types

The fundamental structure is that we're validating a sequence where elements must be properly nested and balanced, which is the classic use case for stack data structures.

3. Approach Evolution

My first instinct is to use a stack-based approach because this is a classic problem that naturally fits the LIFO (Last In, First Out) pattern - whenever we encounter a closing bracket, we need to match it with the most recently opened bracket. But that's O(n²) in worst case if we're doing repeated lookups, let me think about how to optimize this.

The key insight is that we can solve this in linear time with a single pass using a stack. When I process each character from left to right:

• If it's an opening bracket, push it onto the stack
• If it's a closing bracket, check if it matches the top of stack
• If it doesn't match or stack is empty when we need to pop, return false

I notice that if I maintain the invariant that the stack only contains opening brackets and I always match closing brackets with their corresponding opening bracket from the top of stack, I can reduce it to O(n) time by using a hash map for bracket mapping and a single pass through the string.

Let me think about this more carefully. The stack approach is optimal here because:

1. We need to track the order of opening brackets to match them with closing brackets in reverse order
2. Each bracket can only be matched once, so we don't need to revisit elements
3. A stack naturally handles the "last opened, first closed" matching requirement

The key optimization is using a HashMap to store bracket pairs so that I can do O(1) lookup when checking if a closing bracket matches the most recent opening bracket. This eliminates the need for multiple conditional checks and makes the logic clean and efficient.

My final approach will be:

1. Create a HashMap mapping closing brackets to their corresponding opening brackets
2. Iterate through each character in the string
3. For opening brackets, push them onto the stack
4. For closing brackets, check if stack is empty or top doesn't match - return false in either case
5. After processing all characters, return true if stack is empty

The invariant that must hold is that at any point in the algorithm, if we have processed some characters and the stack isn't empty, it contains only opening brackets in proper nesting order.

4. Data Structure Choice

For this valid parentheses problem, I'll use a Stack as my primary data structure.

Primary Data Structures Used

1. Stack (ArrayDeque) - This is the core data structure for solving this problem
2. Character array - To iterate through input string characters

Why Each Data Structure Is Needed

The Stack is essential because:

• It naturally supports the LIFO (Last In, First Out) pattern required for matching parentheses
• When we encounter an opening bracket, we push it onto the stack
• When we encounter a closing bracket, we need to check if it matches the most recently added opening bracket
• Stack's push/pop operations give us O(1) access to the most recent element

The Character array is needed because:

• It allows us to iterate through each character in the input string efficiently
• Java's String.charAt() method provides O(1) access to any character by index

Time and Space Impact

Stack:

• Time: O(1) for push/pop operations
• Space: O(n) in worst case where all characters are opening brackets

Character array:

• Time: O(1) for character access
• Space: O(n) to store the string characters

Helper Structure

I'm using ArrayDeque as a stack implementation because:

• It's more efficient than Stack class (which is synchronized and slower)
• It provides the same push/pop interface
• It's part of the standard Java Collections Framework

The stack will store only the opening brackets: (, [, { - never the closing brackets. This keeps our space usage minimal and focused on what's actually needed for validation.

// Stack implementation choice - ArrayDeque is preferred over Stack
private Deque<Character> stack = new ArrayDeque<>();

5. Algorithm Walkthrough

Let me trace through the algorithm with the example input "(]":

1. Initialize: Stack is empty
2. Process '(':
   • Character is opening bracket, push onto stack
   • Stack: ['(']
3. Process ']':
   • Character is closing bracket
   • Stack top is '(' (matches the closing bracket)
   • Pop from stack
   • Stack: []
4. End of string:
   • Stack is empty
   • Return true

Let me trace through a failing case "(]":

1. Initialize: Stack is empty
2. Process '(':
   • Character is opening bracket, push onto stack
   • Stack: ['(']
3. Process ']':
   • Character is closing bracket
   • Stack top is '(' but we expect ')'
   • No match, return false immediately

Let me trace through the case "([)]":

1. Initialize: Stack is empty
2. Process '(':
   • Character is opening bracket, push onto stack
   • Stack: ['(']
3. Process '[':
   • Character is opening bracket, push onto stack
   • Stack: ['(', '[']
4. Process ')':
   • Character is closing bracket
   • Stack top is '[' but we expect ']'
   • No match, return false immediately

The algorithm correctly handles all these cases by maintaining the LIFO property of the stack and ensuring proper bracket matching. The key invariant is that at any point, if we encounter a closing bracket, the stack must not be empty and the top element must be the corresponding opening bracket.

The algorithm terminates correctly because:

• If all brackets are properly matched, stack will be empty at the end
• If there's a mismatch or unmatched brackets, the algorithm returns false before completion

6. Java Solution

import java.util.*;

public class ValidParentheses {
    public boolean isValid(String s) {
        // Handle edge case of null or empty string
        if (s == null || s.isEmpty()) {
            return true;
        }
        
        // Stack to keep track of opening brackets
        Stack<Character> stack = new Stack<>();
        
        // Map to store closing brackets as keys and their corresponding opening brackets as values
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');
        
        // Iterate through each character in the string
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            
            // If it's an opening bracket, push to stack
            if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
                stack.push(currentChar);
            } 
            // If it's a closing bracket
            else if (currentChar == ')' || currentChar == '}' || currentChar == ']') {
                // If stack is empty, no matching opening bracket
                if (stack.isEmpty()) {
                    return false;
                }
                
                // Pop the top element and check if it matches
                char topElement = stack.pop();
                if (topElement != bracketMap.get(currentChar)) {
                    return false;
                }
            }
        }
        
        // If stack is empty, all brackets were properly matched
        return stack.isEmpty();
    }
}

This solution uses a stack-based approach to validate parentheses matching. The key insight is that we process the string left-to-right and use a stack to track opening brackets. When we encounter a closing bracket, we check if it matches the most recent opening bracket (top of stack). The map lookup provides O(1) matching validation for each closing bracket type.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input string. Each character is processed exactly once, and each stack operation (push/pop) takes O(1) time. The linear traversal dominates the overall complexity.

Space Complexity: O(n) in the worst case, which occurs when all characters are opening brackets and get pushed onto the stack. For example, in the input "((((", the stack will contain all n characters before any matching closing brackets are encountered.

The space complexity is linear because we might need to store up to n/2 opening brackets in the stack at any point during processing, and this can grow linearly with input size.

Why these bounds are correct:

• The algorithm makes a single pass through the string, ensuring O(n) time
• The stack size never exceeds half the input length in the worst case, making O(n) space complexity tight
• Each operation (stack push/pop) is constant time, so no additional factors affect the complexity

Optimality: This solution is optimal for this problem because we must examine each character at least once to determine validity, making O(n) time complexity unavoidable. The stack-based approach is the most efficient way to track bracket nesting, and no better space complexity exists for this constraint.

The solution achieves the best possible trade-off between time and space complexity for the valid parentheses validation problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return true - an empty string has valid parentheses
• Single character: Should return false for both '(' and ')'
• Two characters: Valid combinations like "()" return true, invalid ones like "((" or "))" return false

Duplicate Values and Repeated States

• Multiple nested levels: String like "((()))" should return true
• Mixed nesting: String like "()()" should return true
• Mismatched pairs: String like "(()" or "())" should return false

Boundary Conditions

• Very large input: With 10^4+ characters, ensure stack doesn't overflow
• Alternating patterns: "()()()()" should return true
• Complex nesting: "(()(())())" should return true

Common Implementation Mistakes

• Not handling empty input: Failing to check for empty string before processing
• Incorrect stack operations: Pushing wrong characters or not properly matching closing brackets to opening ones
• Missing validation: Not checking if stack is empty when encountering a closing bracket
• Off-by-one errors: Miscounting or incorrectly tracking stack size
• Not handling invalid closing brackets: Processing ")(" where closing bracket appears before opening bracket

Implementation-specific Pitfalls

• Stack overflow: Using recursive approach instead of iterative for large inputs
• Incorrect character mapping: Not properly associating closing brackets with their opening counterparts
• Missing null checks: Not validating input string for null values in production code
• Inefficient stack operations: Using array-based stacks instead of ArrayDeque for better performance

The solution must carefully handle all these cases while maintaining O(n) time and space complexity.

9. Alternative Approaches

There are several alternative approaches to solving the valid parentheses problem, each with different trade-offs:

Stack-based approach with character mapping: Instead of using a stack to store opening brackets, we can use a HashMap to map closing brackets to their corresponding opening brackets. This allows us to check if the current character matches the top of stack in O(1) time. The space complexity remains the same, but the code becomes slightly more readable.

Recursive approach: We could implement a recursive solution that processes the string character by character, maintaining a counter for unmatched opening brackets. However, this approach has O(n) space complexity due to the call stack and is less intuitive than the iterative stack solution.

Two-pointer approach: For this specific problem, a two-pointer approach is not directly applicable since we need to maintain the order and nesting of brackets. This pattern doesn't naturally fit valid parentheses checking.

State machine approach: We could model this as a finite state machine with states representing the count of unmatched brackets. While theoretically possible, it's overkill for this problem and makes the solution less readable than the stack-based approach.

The stack-based solution is preferred because it's:

• Most intuitive and readable
• Has optimal time complexity O(n)
• Has optimal space complexity O(n) in worst case
• Handles all edge cases naturally
• Easy to extend for multiple bracket types

The stack approach is the most practical and maintainable solution for this problem, with no significant advantages of alternatives that would justify additional complexity.

10. Test Cases

import java.util.*;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
        
        for (char c : s.toCharArray()) {
            if (mapping.containsKey(c)) {
                char topElement = stack.isEmpty() ? '#' : stack.pop();
                if (topElement != mapping.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
    
    // Test cases
    public static void main(String[] args) {
        ValidParentheses solution = new ValidParentheses();
        
        // Test case 1: Valid parentheses
        System.out.println(solution.isValid("()")); // true
        
        // Test case 2: Valid nested parentheses
        System.out.println(solution.isValid("()[]{}")); // true
        
        // Test case 3: Invalid order
        System.out.println(solution.isValid("(]")); // false
        
        // Test case 4: Invalid nesting
        System.out.println(solution.isValid("([)]")); // false
        
        // Test case 5: Valid complex nesting
        System.out.println(solution.isValid("{[()]}")); // true
        
        // Test case 6: Empty string
        System.out.println(solution.isValid("")); // true
        
        // Test case 7: Single opening bracket
        System.out.println(solution.isValid("(")); // false
        
        // Test case 8: Single closing bracket
        System.out.println(solution.isValid(")")); // false
        
        // Test case 9: Odd length string
        System.out.println(solution.isValid("({)}")); // false
        
        // Test case 10: Large valid string
        System.out.println(solution.isValid("((({{[[[((([])))]]]}}}))")); // true
    }
}

Sample Test Cases:

1. Valid parentheses: "()" → true
2. Valid nested parentheses: "()[]{}" → true
3. Invalid order: "(]" → false
4. Invalid nesting: "([)]" → false
5. Valid complex nesting: "{[()]}" → true

Tricky Test Cases:

1. Odd length string: "({)}" → false (odd number of characters)
2. Large valid string: "((({{[[[((([])))]]]}}}))" → true (complex nesting)

Boundary Test Cases:

1. Empty string: "" → true
2. Single opening bracket: "(" → false
3. Single closing bracket: ")" → false

These test cases cover all major scenarios including valid combinations, invalid ordering, nested structures, edge cases with empty or single characters, and complex nesting patterns that ensure the solution handles all possible inputs correctly.

11. Final Summary

The core insight is that valid parentheses form a nested structure that can be efficiently validated using a stack-based approach, where each opening bracket is matched with its corresponding closing bracket in LIFO order. This solution achieves optimal O(n) time complexity and O(n) space complexity by leveraging the stack's natural LIFO behavior to track unmatched opening brackets, making it both correct and efficient for this classic matching problem.