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 reading a book with nested footnotes (like this [1 [2 [3]]]). To understand the sentence, you must:

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

This “Last-In, First-Out” (LIFO) requirement is the fundamental hardware and logical constraint that makes the Stack the optimal data structure.

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

3. Implementation

The key is to use a Map or switch to handle the pairing of brackets.

Java

```java
public boolean isValid(String s) {
    Deque 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();
}
```
</div>


```go
func isValid(s string) bool {
    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
}
```

</div>

---

## 4. Hardware Reality: Why Stack?

You *could* solve this with an 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 push/pop operations.
-   **Temporal Locality**: The most recently added item is the most likely to be accessed next, aligning with CPU cache hierarchies.



        
          
              Metric
              Stack Approach
            

          
              Time Complexity
              O(N) (One pass)
            

              Space Complexity
              O(N) (Worst case)
            

              Data Locality
              High (Sequential Access)
            

        

      

Metric	Stack Approach
Time Complexity	`O(N)` (One pass)
Space Complexity	`O(N)` (Worst case)
Data Locality	High (Sequential Access)