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.

Analogy: The Russian Nesting Dolls

Think of valid parentheses like Russian Nesting Dolls (Matryoshka).

  1. Open a doll (push to stack): You are entering a new nested context.
  2. Open an inner doll (push to stack): You dive deeper into the structure.
  3. Close the inner doll (pop from stack): You must fully assemble the smallest, most-recently-opened doll before you can close the larger outer doll.

If you try to close the outer doll while an inner one is still open, the structure breaks. This physical constraint perfectly models the abstract LIFO property.

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. Anatomy & Step-by-Step Execution

Before jumping into code, let’s break down the system into its core functional components:

Anatomy of a Validator

  1. The State Engine (Stack): Holds the unresolved promises. Every time you see an opening bracket, you make a promise to close it later.
  2. The Dispatcher (Loop): Reads the string sequentially, classifying characters as either “Promises” (opening) or “Fulfillments” (closing).
  3. The Matcher (Validator): When a fulfillment is encountered, it checks the most recent promise (Top of Stack). If they match, the promise is fulfilled. If not, the system immediately rejects the state.

Trace Example: ([{}])

Let’s walk through the exact state transitions for a valid input string:

  1. Read ( -> Promise made. Stack: ['(']
  2. Read [ -> Promise made. Stack: ['(', '[']
  3. Read { -> Promise made. Stack: ['(', '[', '{']
  4. Read } -> Fulfillment. Pop top ({). Matches! Stack: ['(', '[']
  5. Read ] -> Fulfillment. Pop top ([). Matches! Stack: ['(']
  6. Read ) -> Fulfillment. Pop top ((). Matches! Stack: []
  7. End of String: Stack is empty. Result is Valid.

5. 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

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
}

6. 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)