Lab 05 — Stack & Queue Applications: Valid Parentheses + Min Stack

Goal

Master the stack as a structural matching tool, the dual-stack technique for augmented operations, and the queue/deque distinction. The deliverable: validate balanced bracket strings in linear time, then extend to a Min Stack supporting O(1) push, pop, top, getMin.

Background Concepts

LIFO discipline; stack invariants; dual-stack trick for tracking auxiliary state; deque vs queue. Review the Stacks and Queues sections of the Phase 1 README, plus runtime concept 1 (stack vs heap memory).

Interview Context

Valid Parentheses is the warm-up; Min Stack is the follow-up. Together they probe whether you grasp the stack as a general tool (not just a recursion bookkeeping device). Asked at Amazon, Google, Bloomberg, Microsoft. The signal: do you generalize from “match ()” to “match (){}[]”? Do you reach for the dual-stack trick on Min Stack instead of O(N) getMin?

Problem Statement

Part A (Valid Parentheses): Given a string s of bracket characters from (){}[], return true iff every opener is matched with the correct closer in the correct order.

Part B (Min Stack): Design a stack that supports push(x), pop(), top(), and getMin() all in O(1).

Constraints

A: 1 ≤ |s| ≤ 10^4; s contains only the six bracket characters.
B: pop, top, getMin are not called on an empty stack; up to 3 · 10^4 operations.

Clarifying Questions

A: Are non-bracket characters possible? (Per constraints, no — but if extended, ignore them.)
A: Is the empty string valid? (Conventionally yes — vacuous truth.)
B: Are integer values bounded? (Affects whether int suffices.)
B: Is getMin of an empty stack defined? (Per constraints, never called on empty.)
B: Should top and pop be separate, or is pop returning the value acceptable? (LeetCode classic: separate. Match the spec.)

Examples

Input	Output
`"()"`	`true`
`"()[]{}"`	`true`
`"(]"`	`false`
`"([)]"`	`false` (interleaved, not nested)
`"{[]}"`	`true`
`""`	`true`

B: Sequence push(-2), push(0), push(-3), getMin() → -3, pop(), top() → 0, getMin() → -2.

Initial Brute Force

A: Repeatedly scan for adjacent matching pairs (), [], {} and remove them. If string empties, valid; else invalid.

def valid_brute(s):
    while True:
        new = s.replace("()", "").replace("[]", "").replace("{}", "")
        if new == s: break
        s = new
    return s == ""

B: Push x to a normal stack. getMin walks the entire stack each call.

Brute Force Complexity

A: O(N²) worst case (each pass removes constant pairs). B: getMin is O(N) per call, total O(N²) for N operations.

Optimization Path

A: Single pass with a stack: push openers, on closer pop and verify match. B: Maintain a parallel min-stack so each push records the current minimum. On pop, also pop from min-stack. getMin returns the top of min-stack.

Final Expected Approach

A — Valid Parentheses:

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack.pop() != pairs[c]:
                return False
    return not stack

B — Min Stack:

class MinStack:
    def __init__(self):
        self.s = []      # main stack
        self.m = []      # min stack: m[i] = min of s[0..i]

    def push(self, x):
        self.s.append(x)
        self.m.append(x if not self.m else min(x, self.m[-1]))

    def pop(self):
        self.s.pop()
        self.m.pop()

    def top(self):
        return self.s[-1]

    def getMin(self):
        return self.m[-1]

Data Structures Used

A: A single stack of opener characters.
B: Two parallel stacks, both supporting O(1) push/pop.

Correctness Argument

A: Loop invariant — at each iteration, the stack contains the unclosed openers of the prefix of s consumed so far, in order. A closer is valid iff it matches the most-recent opener (LIFO). At end, an empty stack means all openers were closed in order.

B: Invariant — m[i] is min(s[0..i]). When we push x, the new minimum is min(x, current_min) — pure local computation. When we pop, both stacks shrink; the new top of m is correct because it was correct before this push. Hence getMin is m[-1], O(1).

Complexity

A: O(N) time, O(N) space (worst case, all openers). B: O(1) time per operation, O(N) total space.

Implementation Requirements

Use a single map closer → opener to avoid six-way if/else.
For Min Stack, use two stacks (or one stack of pairs); never recompute min by scanning.
Don’t pre-validate s (e.g., for invalid characters) unless the problem demands.
Handle the empty stack case before popping in is_valid.

Tests

A smoke: "()[]{}" valid; "(]" invalid.
A unit: unbalanced opener-only "(("; closer-first ")"; nested correctly "{[]}"; interleaved "([)]".
A edge: empty string; single character.
A large: 10⁴ openers followed by 10⁴ closers; should still run in milliseconds.
B smoke: the canonical sequence above.
B edge: push the same value twice, pop, ensure min is still correct (this is the “duplicate-min trap” — naive single-stack solutions fail here).
Random: generate random op sequences; cross-check against a “min via scan” reference.

Follow-up Questions

A: “What if s may contain other characters (letters, digits)?” → ignore them or treat as “skip.”
A: “Return the index of the first invalid bracket.” → modify the loop to return i instead of False.
A: “Generate all valid bracket strings of length 2N.” → that’s “Generate Parentheses” (Lab 08).
B: “Use only one stack.” → store (value, current_min) as pairs.
B: “Use only constant extra space (no parallel stack).” → encoding trick: store 2x - currentMin when x < currentMin, then decode on pop. Watch for overflow.
B: “Add getMax.” → add a third parallel stack.

Product Extension

A real-time expression evaluator for a spreadsheet engine. As users type formulas, you validate parenthesization on every keystroke (must be O(N) for snappy UX) and maintain a “min/max running aggregate” for selected cells (Min Stack pattern). The two-stack technique generalizes to maintaining any associative aggregate over a stack-shaped sliding context.

Language/Runtime Follow-ups

Python: list is a fast stack via append / pop(). Don’t use list.pop(0) (O(N)).
Java: prefer ArrayDeque over Stack (the latter is synchronized, slower, and inherits from Vector). Deque<Integer> with push / pop / peek.
Go: slices as stacks: s = append(s, x) and x, s = s[len(s)-1], s[:len(s)-1].
C++: std::stack (LIFO adapter) or just std::vector. std::stack’s pop returns void; use top then pop.
JS/TS: Array.push / Array.pop are O(1) amortized. The same array is fine.
Memory: stacks here grow on the heap (the data structure), even though the conceptual abstraction is named “stack.” Don’t confuse with the call stack.

Common Bugs

A — popping an empty stack — Python raises IndexError. Check if not stack first.
A — accepting "((" — forgetting the final if stack check. The string ends with openers still on the stack.
A — wrong pair table — {')': '(', ']': '[', '}': '{'}. Off-by-one easy to typo.
B — naive getMin — scanning the stack is O(N), violating the contract.
B — duplicate-min handling — if you maintain “the min” as a single field and pop the value equal to it without secondary tracking, the min is wrong after pop. Two-stack design avoids this.
B — pop on empty stack — per constraints not called, but if defensive, raise.

Debugging Strategy

A: print the stack and the current char at each step; trace "([)]".
B: print both stacks after each op; verify m[i] == min(s[0..i]).
For the duplicate-min trap, manually trace push(-1), push(-1), pop(), getMin() → must still be -1.

Mastery Criteria

Wrote is_valid cleanly in under 4 minutes; under 5 lines of logic.
Recognized the closer-table pattern over a six-way conditional.
Designed Min Stack with two stacks; explained why one stack with a single min field fails on duplicates.
Sketched the “encoded delta” optimization without needing it.
Handled the empty-stack defensive checks.
Selected ArrayDeque over Stack in Java without prompting.

LeetCode Interview — Extreme Coding