L2. Check for Balanced Parentheses | Stack and Queue

This chapter covers the classic Balanced Parentheses problem, a fundamental coding interview and algorithmic challenge. We examine the core conditions required for a string of brackets to be considered balanced, establish the optimal mental model using a Last-In-First-Out (LIFO) data structure, and walk through a complete implementation with time and space complexity analysis.

1. Problem Statement & The Three Golden Rules

When given a string containing only bracket characters ((, ), {, }, [, ]), our task is to determine whether the string represents a balanced parenthesis sequence.

To be classified as balanced, the string must strictly satisfy three conditions:

1. Matching Pairs: Every opening bracket must have a corresponding closing bracket of the exact same type.
2. Reverse Symmetry: Every closing bracket must have a corresponding opening bracket right before it.
3. Strict Order: Brackets must close in the exact reverse order of how they were opened (proper nesting).

Examples of Valid vs. Invalid Strings

• Balanced: (), ()[]{}, ([{}])
• Unbalanced: (], ([)], (((, )))

2. Core Mental Model: The Last Opening Encountered

If we trace how we mentally verify a balanced string, we notice a recurring behavioral pattern. When we encounter a closing bracket (e.g., )), we immediately look back to check what the last opening bracket was.

Real-Life Analogy: The Cafeteria Tray Stack

Imagine a spring-loaded stack of trays in a cafeteria. When workers clean trays, they place (push) each new tray on top of the stack. When customers need a tray, they always take the top tray—the one that was put there last (LIFO: Last-In, First-Out).

Parentheses work the exact same way: the most recently opened bracket must be the very first one to be closed and popped off.

Because we always need to inspect and validate the most recent opening bracket, a Stack data structure becomes our ideal tool.

3. Step-by-Step Dry Run: Valid String

Let's dry-run a valid string: {[()]} using a stack.

4. Step-by-Step Dry Run: Invalid Scenarios

Handling edge cases is where algorithms are truly tested. Let's look at three failure modes:

Scenario A: Order Violation (([)])

Scenario B: Unclosed Opening Brackets ((()

Scenario C: Orphaned Closing Brackets (]))

5. Algorithmic Pseudo-Code

Below is the structured pseudo-code implementing the balanced parentheses validation algorithm.

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        
        // Condition 1: If it's an opening bracket, push to stack
        if (ch == '(' || ch == '{' || ch == '[') {
            stack.push(ch);
        } 
        // Condition 2: If it's a closing bracket
        else {
            // Edge Case: If stack is empty, we have no matching opening bracket
            if (stack.isEmpty()) {
                return false;
            }
            
            char top = stack.peek();
            
            // Check if closing bracket matches the corresponding opening bracket type
            if ((ch == ')' && top == '(') || 
                (ch == '}' && top == '{') || 
                (ch == ']' && top == '[')) {
                stack.pop(); // Valid pair found, remove opening bracket
            } else {
                return false; // Mismatched bracket types
            }
        }
    }
    
    // Return true only if all opening brackets were successfully matched and popped
    return stack.isEmpty();
}

6. Complexity Analysis

Note: Can the space complexity be optimized further? No. Because every opening bracket must be remembered until its corresponding closing bracket appears downstream, we fundamentally require $O(N)$ auxiliary storage in the worst case.

Summary and Key Takeaways

• Balanced Parenthesis Definition: Requires matching pairs, strict reverse symmetry, and proper nesting order.
• Why Stacks?: Stacks follow a Last-In-First-Out (LIFO) model, making them the perfect data structure for tracking the last opening bracket encountered.
• Handling Opening Brackets: Whenever an opening bracket ((, {, [) is found, push it directly onto the stack.
• Handling Closing Brackets: When a closing bracket is found, verify that the stack is not empty, peek/pop the top element, and confirm it is the exact matching counterpart.
• Orphaned Closings: If a closing bracket arrives while the stack is empty, the string is immediately invalid (return false).
• Final Stack Check: At the end of iteration, the stack must be completely empty. If elements remain, it indicates unclosed opening brackets.
• Optimal Efficiency: The approach runs in optimal $O(N)$ time and $O(N)$ space.