Valid Parentheses: LIFO in Action

[!NOTE] This module explores the core principles of the Valid Parentheses problem, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Genesis of the Stack

Most developers memorize that “Parentheses = Stack”. But why?

Imagine you are a compiler parsing nested code blocks, or a reader following a book with nested footnotes (like this [1 [2 [3]]]?). To understand the context, you must:

1. Encounter an opening bracket [.
2. Maintain its “state” while reading nested content.
3. Ensure the most recently opened bracket is the first one closed.

This “Last-In, First-Out” (LIFO) requirement is the fundamental logical constraint that makes the Stack the optimal data structure. An array or queue processes linearly, but a stack mirrors the nested nature of the problem perfectly.

---

2. Problem Definition & Edge Cases

Before diving into the stack mechanics, we must define the exact constraints of the problem. You are given a string s containing just the characters '(', ')', '{', '}', '[' and ']'. Determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Edge Cases to Consider

• Empty String: Usually valid by default, though constraints may enforce $1 \le s.length$.
• Odd Length String: Impossible to be valid. Early return optimization: if (s.length() % 2 != 0) return false;.
• All Opening Brackets: e.g., ((((. The string is fully processed, but the stack is not empty at the end.
• Starting with Closing Bracket: e.g., ]()[. Immediate failure upon encountering a mismatched closing bracket.

---

3. Interactive Analysis

Visualize how the stack maintains state. Each opening bracket is a “promise” that must be fulfilled by its corresponding closing partner.

Input: ({[]})

LIFO Stack

Execution Step

Click 'Next Step' to begin.

---

4. Implementation

The key is to use a stack structure (like a Deque in Java or a slice in Go) to maintain state. We can employ a clever mapping strategy to pair brackets efficiently. Note the addition of the odd-length early return optimization.

Java

Go

Java

public boolean isValid(String s) {
    // Early return: An odd-length string cannot be valid
    if (s.length() % 2 != 0) return false;

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

Go

func isValid(s string) bool {
    // Early return: An odd-length string cannot be valid
    if len(s) % 2 != 0 {
        return false
    }

    stack := []rune{}
    pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}

    for _, char := range s {
        if open, ok := pairs[char]; ok {
            if len(stack) == 0 || stack[len(stack)-1] != open {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, char)
        }
    }
    return len(stack) == 0
}

---

5. Hardware Reality: Why Stack?

You could solve this with a dynamically sizing array and a pointer, but a Stack is conceptually closer to how the CPU handles Memory Indirection and Recursion.

• Memory Locality: A stack typically grows in a contiguous memory block, ensuring high cache hit rates during sequential push/pop operations.
• Temporal Locality: The most recently added item is the most likely to be accessed next, aligning perfectly with CPU cache hierarchies (L1/L2 caches).

Metric	Stack Approach
Time Complexity	O(N) (One pass through the string)
Space Complexity	O(N) (Worst case, all open brackets)
Data Locality	High (Sequential Access aligns with hardware caches)