Valid Parentheses Problem Solution

The valid parentheses problem checks 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 programming interviews.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected input size and constraints? (e.g., max string length, character set)
2. Are we allowed to mutate the input array/structure?
3. Should we return a boolean or the index of the first invalid parenthesis?
4. Can the input contain characters other than parentheses, or only '(', ')', '{', '}', '[', ']'?
5. What is the target time complexity for follow-up? O(n) is expected but let me know if there's a specific constraint.

Restate the pattern or problem type in your own words: The valid parentheses problem checks whether a string of brackets is properly nested and matched. For every opening bracket, there must be a corresponding closing bracket in the correct order.

Clarify the signal words and constraint shape that point to it:

• Signal words: "valid", "balanced", "matching", "nesting"
• Constraint shape: String with bracket characters, must satisfy LIFO (Last In First Out) property for matching pairs
• The problem requires maintaining a stack-like relationship between opening and closing brackets

Note any assumptions you are making:

• Input contains only bracket characters: '(', ')', '{', '}', '[', ']'
• We're checking for proper nesting and matching, not content validity
• The string length is reasonable (not millions of characters for practical purposes)

Identify whether the pattern is best suited for static, streaming, or online scenarios: This is a static problem where we process the entire input once. It's not streaming since we need to know all brackets before determining validity, but it could be adapted for online checking if we were to process brackets one at a time and track the stack state.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Valid" or "well-formed" expressions
• Problems involving matching pairs of symbols (parentheses, brackets, braces)
• "Balance" or "proper nesting" requirements
• Input consists of only specific character types (e.g., ()[]{}
• "Return true/false" or "determine validity" as output

Why this pattern fits better than alternatives: This is fundamentally a stack-based matching problem. Unlike other approaches like recursion or two-pointer techniques, the stack pattern naturally handles nested structures and maintains the LIFO (Last In, First Out) property required for proper bracket matching. The stack approach is more intuitive and efficient than trying to simulate nested parsing with recursion or maintaining complex counters.

Conditions where variations apply:

• Counters approach: When only checking if the total count matches (not nesting), but this fails for order validation (e.g., ([)] vs ()[])
• Recursion with backtracking: When the problem requires tracking multiple levels of nesting or complex nested structures beyond simple bracket matching
• State machine: When the problem involves more complex token validation or when the input contains multiple types of tokens beyond just brackets

Core insight that makes this pattern work: The key insight is that brackets must close in the reverse order they opened. This LIFO property makes a stack the perfect data structure to validate proper nesting and matching of brackets. Each opening bracket is pushed onto the stack, and each closing bracket must match the most recently opened bracket (top of stack).

This pattern is particularly effective for problems where:

1. Bracket types must be matched correctly ((), [], {})
2. Nesting depth matters (e.g., ([]{}) is valid, but ([)] is not)
3. The solution requires tracking the order of opening brackets to ensure proper closing sequence

3. Approach Evolution

Interview communication script:

"My first instinct is to use a stack-based approach because this is a classic matching problem where we need to ensure that opening and closing brackets are properly nested. But let me think about this more carefully - if I simply push opening brackets and pop when I see closing ones, that should work for basic cases. However, I need to be more systematic about it.

Let me think about the constraints and what we're really trying to solve here. We need to validate that parentheses are properly matched - that means every opening bracket has a corresponding closing bracket in the right order.

The brute force approach would be to repeatedly scan and remove matching pairs, but that's O(n²) because in worst case we'd have to scan the entire string multiple times. That's clearly inefficient.

I notice that if I maintain a stack invariant - where the stack always contains unmatched opening brackets in proper order - I can reduce this to O(n) time complexity by making just one pass through the string.

Let me trace through this more carefully: I'll process each character once, and for opening brackets I push them onto the stack, for closing brackets I check if they match the most recent opening bracket. If they don't match or the stack is empty when I try to pop, it's invalid.

The key insight is that we only need to track the most recent unmatched opening bracket, which makes a stack the perfect data structure here. This approach is optimal because we can't do better than O(n) time since we must examine each character at least once, and O(n) space in worst case where all characters are opening brackets."

Brute-force approach: Repeatedly scan string and remove matching pairs until no more can be removed. This is O(n²) time complexity because in worst case we might need to scan the entire string multiple times, and O(n) space for storing intermediate strings.

Improved approach: Use a stack to maintain unmatched opening brackets. For each character in the string, if it's an opening bracket, push it onto stack; if it's a closing bracket, check if it matches the top of stack. This reduces to O(n) time and O(n) space.

Final approach with step-by-step reasoning:

1. Process input string character by character from left to right
2. When encountering an opening bracket ((), [], {}), push it onto stack
3. When encountering a closing bracket, check if it matches the most recent opening bracket (top of stack)
4. If mismatch or stack empty when trying to pop, return false
5. After processing all characters, return true if stack is empty (all brackets matched)

Important invariants that must hold:

• Stack always contains only unmatched opening brackets in proper order
• At any point, if we encounter a closing bracket and stack is empty, it's invalid
• At end of processing, stack must be empty for valid parentheses

4. Data Structure Choice

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

Primary Data Structures Used

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

Why Each Data Structure Is Needed

The Stack is essential because:

• It naturally supports the LIFO (Last In, First Out) principle required for matching parentheses
• We can push opening brackets and pop when we encounter closing brackets
• It allows us to efficiently check if the most recent unmatched opening bracket matches the current closing bracket
• Stack operations (push/pop) are O(1) time complexity

The Character array/string is needed to:

• Provide the input sequence to process
• Allow iteration through each character to determine bracket types

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/string:

• Time: O(n) to iterate through all characters
• Space: O(n) for storing the input

Helper Structure

I'm using ArrayDeque as my stack implementation because:

• It provides O(1) operations for both push and pop
• It's more efficient than traditional Stack class in Java
• It's a direct implementation of the Deque interface with better performance characteristics

The stack will only store opening brackets: '(', '[', '{' - never closing brackets, which makes the matching logic clean and efficient.

This choice enables a clean implementation where we can process each character once and maintain the necessary state for validation without needing additional complex data structures.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: "( ) [ ] { }"

Step 1: Process '('

• Stack is empty, push '('
• Stack: ['(']

Step 2: Process ')'

• Top of stack is '(' which matches current closing bracket
• Pop from stack
• Stack: []

Step 3: Process '['

• Stack is empty, push '['
• Stack: ['[']

Step 4: Process ']'

• Top of stack is '[' which matches current closing bracket
• Pop from stack
• Stack: []

Step 5: Process '{'

• Stack is empty, push '{'
• Stack: [ '{' ]

Step 6: Process '}'

• Top of stack is '{' which matches current closing bracket
• Pop from stack
• Stack: []

Final State: Stack is empty, all brackets matched correctly → return true

The key invariants maintained throughout the process:

1. Stack only contains opening brackets
2. When we encounter a closing bracket, it must match the most recent opening bracket (top of stack)
3. At end, stack should be empty for valid expression

Edge Case Handling:

• If we encounter a closing bracket when stack is empty → return false immediately
• If stack is not empty at end → return false

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> bracketMap = new HashMap<>();
    bracketMap.put(')', '(');
    bracketMap.put(']', '[');
    bracketMap.put('}', '{');
    
    for (char c : s.toCharArray()) {
        if (bracketMap.containsKey(c)) { // Closing bracket
            if (stack.isEmpty() || stack.pop() != bracketMap.get(c)) {
                return false;
            }
        } else { // Opening bracket
            stack.push(c);
        }
    }
    
    return stack.isEmpty();
}

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 and their corresponding opening brackets
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');
        
        // Iterate through each character in the string
        for (char c : s.toCharArray()) {
            // If it's an opening bracket, push to stack
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } 
            // If it's a closing bracket
            else if (c == ')' || c == '}' || c == ']') {
                // If stack is empty, no matching opening bracket
                if (stack.isEmpty()) {
                    return false;
                }
                
                // Pop the last opening bracket and check if it matches
                char top = stack.pop();
                if (top != bracketMap.get(c)) {
                    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. For each character in the string, we either push opening brackets onto the stack or check that closing brackets match the most recent opening bracket. The use of a HashMap makes the bracket matching logic clean and extensible.

7. Complexity Analysis

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

Space Complexity: O(n) in the worst case, which occurs when all characters are opening brackets (like (((). In this scenario, the stack will contain all n characters. In the best case with valid balanced parentheses, space usage is O(n/2) = O(n) for half the characters in the stack.

The bounds are tight because:

• We must examine every character at least once to validate the structure
• The stack size is directly proportional to the number of unmatched opening brackets
• No operations can be skipped or reduced in complexity

This solution is optimal for the problem as stated. Any algorithm that validates parentheses must at minimum process each character once, making O(n) time complexity unavoidable. The space complexity is also optimal since we need to store at most all opening brackets in the worst case.

The solution achieves the best possible complexity trade-off for this constraint satisfaction problem, with linear time and space matching the information-theoretic lower bounds.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return true - an empty string has valid parentheses
• Single character: Should return false - a single parenthesis cannot be balanced
• Two characters: Valid combinations like "()" return true, invalid ones like ")(" return false

Duplicate Values and Repeated States

• Multiple nested structures: "(())" should return true - properly nested parentheses
• Mixed types: "[({})]" should return true - mixed bracket types properly matched
• Repeated patterns: "()[]{}" should return true - valid mixed brackets

Boundary Conditions

• Only opening brackets: "(((" should return false - unmatched opening brackets
• Only closing brackets: ")))" should return false - unmatched closing brackets
• Alternating patterns: ")()()" should return false - starts with closing bracket
• Large input size: For very large strings, stack overflow risk exists (though Java handles this well with reasonable input sizes)

Common Implementation Mistakes

• Not checking for empty input: Failing to handle edge case of empty string
• Incorrect stack operations: Pushing wrong elements or popping from empty stack without checking
• Missing bracket type handling: Only checking for () but ignoring [] and {}
• Wrong return logic: Returning true when stack is not empty or false when it's empty
• Not handling mismatched brackets: For example, "([)]" - should return false but might pass if logic is flawed
• Stack underflow: Attempting to pop from empty stack without proper bounds checking

The most critical pitfall is failing to validate that the stack isn't empty when trying to pop - this will cause a runtime exception in most implementations.

9. Alternative Approaches

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

Stack-based approach with character counting: Instead of using a stack to track opening brackets, we could maintain counters for each bracket type and validate their balance. This works well for problems with only one type of bracket, but becomes unwieldy with multiple bracket types where order matters.

Recursive approach with backtracking: We could implement a recursive solution that tries to match each opening bracket with its corresponding closing bracket. While this is conceptually clean, it introduces O(n) recursion depth and can be harder to debug than the iterative stack solution.

Two-pointer approach: For some variants like validating parentheses in a string, we might consider using two pointers to traverse from both ends. However, this approach fails for cases where brackets are nested or interleaved, making it unsuitable for the general valid parentheses problem.

State machine approach: We could model this as a finite state automaton with states representing the current nesting level of different bracket types. While theoretically sound and useful for parsing applications, it's more complex to implement than the stack-based solution and offers no performance advantage.

The stack-based approach is preferred because it's intuitive, efficient, and handles all bracket nesting patterns correctly. It's the most maintainable solution that scales well with additional bracket types and provides clear error handling for malformed expressions.

The stack solution is optimal for this problem because it naturally models the LIFO (Last In, First Out) property of valid bracket matching, making it both conceptually and practically the best choice.

10. Test Cases

import java.util.*;

public class ValidParenthesesTestCases {
    
    public static void main(String[] args) {
        // Test case 1: Basic valid parentheses
        // Input: "()"
        // Expected: true
        System.out.println("Test 1 - Basic valid: " + isValid("()"));
        
        // Test case 2: Nested valid parentheses
        // Input: "()[]{}"
        // Expected: true
        System.out.println("Test 2 - Nested valid: " + isValid("()[]{}"));
        
        // Test case 3: Invalid nesting
        // Input: "([)]"
        // Expected: false
        System.out.println("Test 3 - Invalid nesting: " + isValid("([)]"));
        
        // Test case 4: Single type valid
        // Input: "((()))"
        // Expected: true
        System.out.println("Test 4 - Single type valid: " + isValid("((()))"));
        
        // Test case 5: Single type invalid
        // Input: "((())"
        // Expected: false
        System.out.println("Test 5 - Single type invalid: " + isValid("((())"));
        
        // Test case 6: Empty string
        // Input: ""
        // Expected: true
        System.out.println("Test 6 - Empty string: " + isValid(""));
        
        // Test case 7: Single character
        // Input: "("
        // Expected: false
        System.out.println("Test 7 - Single character: " + isValid("("));
        
        // Test case 8: Complex valid case
        // Input: "{[()]}()"
        // Expected: true
        System.out.println("Test 8 - Complex valid: " + isValid("{[()]}()"));
        
        // Test case 9: Too many closing brackets
        // Input: "([{}])})"
        // Expected: false
        System.out.println("Test 9 - Too many closing: " + isValid("([{}])})"));
        
        // Test case 10: Mixed invalid order
        // Input: "{[(])}"
        // Expected: false
        System.out.println("Test 10 - Mixed invalid order: " + isValid("{[(])}"));
    }
    
    public static boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        
        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)) {
                if (stack.isEmpty() || stack.pop() != mapping.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}

Sample Test Cases:

1. Basic valid parentheses: "()" → true
2. Nested valid parentheses: "()[]{}" → true
3. Invalid nesting: "([)]" → false
4. Single type valid: "((()))" → true
5. Single type invalid: "((())" → false
6. Empty string: "" → true
7. Single character: "(" → false
8. Complex valid case: "{[()]}()" → true
9. Too many closing brackets: "([{}])})" → false
10. Mixed invalid order: "{[(])}" → false

Key Test Coverage:

• Valid and invalid combinations of all three bracket types
• Empty and minimal inputs
• Mismatched bracket counts
• Incorrect nesting order
• Complex nested structures
• Boundary conditions with single characters

11. Final Summary

The core idea is to use a stack-based approach to validate that parentheses are properly nested and matched, where each closing bracket must correspond to the most recent unmatched opening bracket. This solution works efficiently by processing the input sequentially and maintaining a simple stack of expected closing brackets, making it both time and space optimal for this specific validation problem. The elegance lies in the direct correspondence between opening and closing brackets, which naturally maps to a LIFO (Last-In-First-Out) stack data structure.