The Complete DSA Pattern Bible

Suppose `will_it_halt(func)` exists.
Now write an evil function `paradox()`:

def paradox():
    if will_it_halt(paradox) == True:
        while True: pass  # Loop forever!
    else:
        return            # Halt immediately!

💥 If paradox() halts, will_it_halt() predicted it loops forever (WRONG!)
💥 If paradox() loops forever, will_it_halt() predicted it halts (WRONG!)

┌──────────────────────────────────────┬─────────────────────────────────────────────────────────┐
│ System                               │ How It Accidentally Becomes An Infinite Loop            │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ SQL Databases (PostgreSQL / MySQL)   │ `WITH RECURSIVE` CTEs can loop infinitely, pegging CPU. │
│ Regex Engines                        │ Catastrophic Backtracking on expressions like (a+)+$    │
│ TypeScript Type Systems              │ Recursive type definitions can hang the compiler.       │
│ CSS (CSS3 Selectors & Checkboxes)    │ Cellular automata can be simulated entirely in CSS.     │
└──────────────────────────────────────┴─────────────────────────────────────────────────────────┘

# ❌ TRAP: Infinite loop / Stack Overflow!
def binary_search(nums, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        # 💥 BUG: Forgot to add +1! If low == mid, range never shrinks!
        return binary_search(nums, mid, high, target)
    else:
        return binary_search(nums, low, mid - 1, target)

# ✅ SENIOR FIX: Always strictly advance bounds
return binary_search(nums, mid + 1, high, target)

# ❌ TRAP: If nums[left] and nums[right] do not match any branch,
# pointers never move, causing a live-lock infinite loop!
while left < right:
    if nums[left] + nums[right] == target:
        return [left, right]
    elif nums[left] + nums[right] < target:
        left += 1
    # 💥 BUG: Missing `else: right -= 1` branch!

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🟢 P (Polynomial Time)    = Easy to SOLVE (Sorting, BFS, Binary Search)     │
│ 🟡 NP (Nondet. Poly Time) = Hard to solve, but Easy to VERIFY (Sudoku)      │
│ 🔴 NP-Complete            = The hardest problems in NP (If one is solved,   │
│                             ALL are solved: P = NP!)                        │
│ 🟣 NP-Hard                = At least as hard as NP-Complete (e.g., Halting) │
└─────────────────────────────────────────────────────────────────────────────┘

Constraint Reality Check:
• If W = 1,000 and N = 100:     N · W = 100,000 operations ➔ Runs in 2 milliseconds (PASS!)
• If W = 10^9 and N = 100:       N · W = 10^11 operations  ➔ Takes 20 minutes (💥 TLE & Out of Memory!)

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🚗 Big-O (Upper Bound)    = The Speed Limit: "You won't exceed 70 mph"      │
│ 🛑 Big-Ω (Lower Bound)    = The Minimum Speed: "Traffic forces at least 15" │
│ 🎯 Big-Θ (Tight Bound)    = Cruise Control: "Locked exactly at 55 mph"      │
└─────────────────────────────────────────────────────────────────────────────┘

Fastest                                                                 Slowest
O(1) ─── O(log N) ─── O(√N) ─── O(N) ─── O(N log N) ─── O(N²) ─── O(2^N) ─── O(N!)
 Instant   Binary      Prime    Linear   MergeSort    Nested   Subsets   Permutations
 Lookup    Search      Check     Scan                 Loops

Array in RAM (Contiguous):
[ 42 ][ 17 ][ 99 ][ 04 ][ 88 ][ 12 ][ 31 ][ 64 ]
 └───────────── 64-Byte CPU Cache Line ─────────────┘
  ➜ 1 Memory Access fetches 16 integers at once! Cache Hit ≈ 1 nanosecond.

Linked List in RAM (Scattered Pointers):
[ Node A ] ──(Pointer)──> [ Node B (Address +4MB) ] ──(Pointer)──> [ Node C (Address -2MB) ]
 ➜ Every pointer jump triggers a CPU Cache Miss! RAM roundtrip ≈ 50-100 nanoseconds.

# ❌ TRAP: O(N^2) Time Complexity!
# In Python, Java, and C#, strings are immutable.
# Each `+` allocates a NEW string and copies all previous characters!
s = ""
for ch in char_list:  # Runs N times
    s += ch  # Copies 1 + 2 + 3 + ... + N = O(N^2) total chars

# ✅ SENIOR FIX: O(N) Time Complexity
s = "".join(char_list)  # Pre-sizes the buffer once; runs in O(N)

# ❌ TRAP: O(N^2) Time Complexity!
# In Python, arr[1:] copies the entire remaining list of length K!
def process(arr):
    while arr:
        val = arr[0]
        arr = arr[1:]  # Copies N-1, N-2, N-3... elements = O(N^2)

# ✅ SENIOR FIX: O(N) using an Index Pointer
def process(arr):
    for i in range(len(arr)):
        val = arr[i]  # O(1) index access

[ 👔 CEO (Root) ]  ────────── Work done at top: f(N)
                     /         \
          [ 🏢 VP 1 ]           [ 🏢 VP 2 ]  ── Sub-problems delegated
            /     \               /     \
         [Mgr]   [Mgr]         [Mgr]   [Mgr]
         /   \   /   \         /   \   /   \
       [👷] [👷] [👷] [👷]   [👷] [👷] [👷] [👷]  ── Ground workers (Leaves, N=1)

┌─────────────────────────────────────────────────────────────────────────────┐
│ 1. CEO does all the work?        ➜ O(f(N))     (Root Dominates)             │
│ 2. Everyone does equal work?     ➜ O(f(N) · log N) (Balanced Tree)          │
│ 3. Ground workers do all work?   ➜ O(Leaves)   (Leaves Dominate)            │
└─────────────────────────────────────────────────────────────────────────────┘

Level 0:                 [ N ]                     = N work
                         /   \
Level 1:           [ N/2 ]   [ N/2 ]               = N/2 + N/2 = N work
                    /   \     /   \
Level 2:        [N/4]  [N/4] [N/4]  [N/4]          = 4 * (N/4) = N work
... (log N levels total)
────────────────────────────────────────────────────────────────────────
Total Work = N * log₂ N

High Memory
┌────────────────────────────────────────────────────────┐
│ Stack Frame 3: dfs(node.left.left)                     │
│  - Return Address: 0x7fff4820                          │
│  - Local variables, parameter pointers (64-128 bytes)  │
├────────────────────────────────────────────────────────┤
│ Stack Frame 2: dfs(node.left)                          │
├────────────────────────────────────────────────────────┤
│ Stack Frame 1: dfs(root)                               │
└────────────────────────────────────────────────────────┘
Low Memory (Stack grows downward towards Heap)

# ❌ TRAP: O(N log N) Extra Space and O(N^2) Time!
# `nums[:mid]` copies the elements into a new list at every call!
def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])   # 💥 Creates a copy!
    right = merge_sort(nums[mid:])  # 💥 Creates a copy!
    return merge(left, right)

# ✅ SENIOR FIX: Pass Index Pointers (O(log N) Space)
def merge_sort(nums, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    merge_sort(nums, left, mid)
    merge_sort(nums, mid + 1, right)

Append 1: [ A ]               Cost = 1 op
Append 2: [ A | B ]           Cost = 1 op
Append 3: [ A | B | C | _ ]   Array full! Resize to 4: Copy A, B, insert C ➜ Cost = 3 ops
Append 4: [ A | B | C | D ]   Cost = 1 op
Append 5: [ A | B | C | D | E | _ | _ | _ ] Resize to 8: Copy 4, insert E ➜ Cost = 5 ops

left = 0
for right in range(len(nums)):  # Outer loop runs N times
    window_sum += nums[right]
    while window_sum > target:  # Inner while loop! Is this O(N^2)??
        window_sum -= nums[left]
        left += 1  # ⚠️ Notice: `left` NEVER resets backward!

stack = []
for x in nums:  # Runs N times
    while stack and stack[-1] < x:  # Inner loop popping elements!
        stack.pop()
    stack.append(x)

Push element 1 ──┐
Push element 2 ──┼──> Exactly N total pushes across entire program
Push element 3 ──┘

Pop element 1 ──┐
Pop element 2 ──┼──> At most N total pops across entire program
Pop element 3 ──┘
─────────────────────────────────────────────────────────────
Total operations across all iterations ≤ 2N = O(N)

Latency Timeline:
Append 1..1023:  [0.01 ms] [0.01 ms] [0.01 ms] ... (Fast)
Append 1024:     [ 15.0 ms ] 💥 Resizing array from 1024 to 2048! (P99 Spike / Audio Glitch)
Append 1025..:   [0.01 ms] [0.01 ms] ...

# ❌ TRAP: O(N^2) Time Complexity!
# A Python list is a dynamic contiguous array.
# Calling `pop(0)` removes the first element and SHIFTS all remaining N-1 elements left!
queue = [1, 2, 3, 4, 5]
while queue:
    item = queue.pop(0)  # O(N) shift per iteration! O(N^2) total!

# ✅ SENIOR FIX: O(N) using collections.deque (Doubly Linked Blocks)
from collections import deque
queue = deque([1, 2, 3, 4, 5])
while queue:
    item = queue.popleft()  # True O(1) pointer unlink! O(N) total!

# ❌ TRAP: Re-setting left = 0 destroys the amortized bound!
if invalid_condition:
    left = 0  # 💥 Can cause up to N pointer resets ➔ Degrades to O(N^2)!

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🛑 THE COMPARISON LOWER BOUND:                                              │
│ No comparison-based sorting algorithm (MergeSort, QuickSort, HeapSort)      │
│ can EVER run faster than Ω(N log N) in the worst case!                      │
└─────────────────────────────────────────────────────────────────────────────┘

┌───────────────────┬──────────────────────┬─────────────────────────────────────────────────────────┐
│ Language          │ Algorithm            │ Why This Hybrid Architecture?                           │
├───────────────────┼──────────────────────┼─────────────────────────────────────────────────────────┤
│ Python & Java     │ Timsort              │ MergeSort + InsertionSort hybrid. Detects naturally     │
│ (Objects)         │                      │ ordered runs. Stable (preserves object identity order). │
├───────────────────┼──────────────────────┼─────────────────────────────────────────────────────────┤
│ C++ (`std::sort`) │ Introsort            │ QuickSort + HeapSort + InsertionSort. Starts fast with  │
│                   │                      │ QuickSort; switches to HeapSort if depth > 2 log N      │
│                   │                      │ to avoid O(N²) worst-case degradation.                  │
└───────────────────┴──────────────────────┴─────────────────────────────────────────────────────────┘

# ❌ TRAP: Out Of Memory!
# nums = [1, 10^9]. Range K = 10^9!
# Allocating a count array of size 1,000,000,000 crashes with MemoryError!
def bad_counting_sort(nums):
    max_val = max(nums)
    counts = [0] * (max_val + 1)  # 💥 Allocates gigabytes of RAM!

# ✅ SENIOR FIX: Only use Counting Sort when max(nums) - min(nums) ≤ 10^5.
# Otherwise, fall back to O(N log N) Timsort.

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🎭 POLYNOMIAL REDUCTION (A ≤ₚ B):                                           │
│ "Problem A reduces to Problem B" means:                                     │
│ If we have a solver for B, we can solve A with only a tiny polynomial       │
│ amount of translation work upfront.                                         │
└─────────────────────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────┬─────────────────────────────────────────────────────────┐
│ Infrastructure Component             │ Underlying Intractable Problem                          │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ Kubernetes Pod Scheduler             │ Bin Packing: Fitting variable CPU/RAM pods into VMs     │
│ SQL Query Planner (10+ Table Joins)  │ Traveling Salesperson: Finding optimal join order       │
│ Package Managers (npm, pip, cargo)   │ Boolean SAT: Resolving version dependency trees         │
│ CDN Edge Cache Placement             │ Facility Location Problem: Minimizing latency to users  │
└──────────────────────────────────────┴─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────────┐
│ 📐 APPROXIMATION ALGORITHM:                                                 │
│ An algorithm that runs in fast polynomial time (e.g., O(N) or O(N log N))   │
│ and provides a MATHEMATICAL GUARANTEE that its result is within a bounded   │
│ factor (e.g., at most 2×) of the theoretical optimum.                       │
└─────────────────────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────┬─────────────────────────────────────────────────────────┐
│ System Problem                       │ Approximation Strategy                                  │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ Microservice Load Balancing          │ "The Power of Two Choices": Pick 2 random backend       │
│                                      │ servers and send traffic to the less loaded one.        │
│                                      │ (Achieves near-perfect balance with zero central lock!) │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ Database Unique Visitor Counting     │ HyperLogLog: Approximates unique counts (CARDINALITY)   │
│                                      │ within 1% error using only 1.5 KB of RAM!               │
└──────────────────────────────────────┴─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🎰 LAS VEGAS ALGORITHM:                                                     │
│ Always gives the 100% CORRECT answer, but RUNTIME depends on luck.          │
│ • Example: QuickSort with a random pivot.                                   │
│ • It will NEVER return a corrupted or mis-sorted array. Worst case is slow, │
│   but expected runtime is always O(N log N).                                │
├─────────────────────────────────────────────────────────────────────────────┤
│ 🎲 MONTE CARLO ALGORITHM:                                                   │
│ Always finishes in FIXED FAST TIME, but has a tiny chance of error.         │
│ • Example: Bloom Filter, Miller-Rabin Primality Test.                       │
│ • "It might say Yes when it means No (false positive), but it never misses  │
│   a real match, and runs in 1 microsecond."                                 │
└─────────────────────────────────────────────────────────────────────────────┘

def partition3(nums, low, high, pivot):
    lt = low       # nums[low..lt-1] < pivot
    gt = high      # nums[gt+1..high] > pivot
    i = low        # nums[lt..i-1] == pivot
    while i <= gt:
        if nums[i] < pivot:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1
            i += 1
        elif nums[i] > pivot:
            nums[gt], nums[i] = nums[i], nums[gt]
            gt -= 1
        else:
            i += 1
    return lt, gt  # All elements between lt and gt are EQUAL to pivot!

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🧭 HEURISTIC:                                                               │
│ A computational rule of thumb that estimates the distance to the goal.      │
│ It does not guarantee perfection on its own, but it guides the search away  │
│ from billions of dead-end paths.                                            │
└─────────────────────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────┬─────────────────────────────────────────────────────────┐
│ Real-World System                    │ Heuristic Technique Used                                │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ Google Maps / GPS Routing            │ A* with Contraction Hierarchies: Precomputes highway    │
│                                      │ shortcuts to route across countries in 10 ms.           │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ PostgreSQL Query Planner             │ Genetic Query Optimizer (`GEQO`): When an SQL query     │
│                                      │ joins > 12 tables, exhaustive search is too slow;       │
│                                      │ Postgres uses heuristic genetic search for join plans.  │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ Chess & Game AI                      │ Alpha-Beta Pruning: Discards entire minimax subtrees    │
│                                      │ that the opponent will never allow you to enter.        │
└──────────────────────────────────────┴─────────────────────────────────────────────────────────┘

# ❌ BUG: State persists into sibling branches!
visited.add(next_node)
backtrack(next_node)
# 💥 BUG: Forgot `visited.remove(next_node)`!

┌─────────────────────────────────────────────────────────────────────────────┐
│ 💾 HUFFMAN ENCODING:                                                        │
│ Use a Min-Heap to repeatedly merge the two lowest-frequency symbols.        │
│ Produces a prefix-free optimal binary tree in O(N log N) time.              │
└─────────────────────────────────────────────────────────────────────────────┘

Original n:      1 0 1 1 0 0    (Decimal 44)
n - 1:           1 0 1 0 1 1    (Flips lowest set bit and trailing zeros)
n & (n - 1):     1 0 1 0 0 0    ➜ Lowest set bit is erased in 1 operation!

# ❌ TRAP: Evaluates as `n & (1 == 0)` which is always 0!
if n & 1 == 0:
    print("Even")

# ✅ SENIOR FIX: Always wrap bitwise operations in parentheses!
if (n & 1) == 0:
    print("Even")

┌─────────────────────────────────────────────────────────────────────────────┐
│ ⚡ AMDAHL'S LAW:                                                            │
│ If a fraction (1 - P) of your program is serial, your maximum possible      │
│ speedup on infinite processors is capped at:                                │
│                     Speedup ≤ 1 / (1 - P)                                   │
│ • If 50% is serial ➜ Max speedup is 2×                                      │
│ • If 10% is serial ➜ Max speedup is 10×                                     │
│ • If 1% is serial  ➜ Max speedup is 100×                                    │
└─────────────────────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────┬─────────────────────────────────────────────────────────┐
│ System                               │ CAP Stance during Network Partitions                    │
├──────────────────────────────────────┼─────────────────────────────────────────────────────────┤
│ PostgreSQL / MySQL (Primary-Replica) │ CP: Refuses inconsistent writes to preserve data safety │
│ Cassandra / DynamoDB (AP Mode)       │ AP: Accepts local writes, reconciles with Eventual      │
│                                      │     Consistency (Vector Clocks / LWW)                   │
└──────────────────────────────────────┴─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────────────────┐
│ 🏥 VITAL SIGN 1: What is the size of N? (10, 10³, 10⁵, 10⁹?)                │
│ 🏥 VITAL SIGN 2: Is the input sorted or can it be sorted?                   │
│ 🏥 VITAL SIGN 3: Are negative numbers allowed?                              │
│ 🏥 VITAL SIGN 4: Are we finding an exact match, an optimum, or all combos?  │
└─────────────────────────────────────────────────────────────────────────────┘

# ❌ BUG: Modifying list while iterating causes skipped elements!
for item in my_list:
    if condition(item):
        my_list.remove(item)

# ✅ SENIOR FIX: List comprehension or index iteration backwards
my_list = [item for item in my_list if not condition(item)]

[ Box 0 ] [ Box 1 ] [ Box 2 ] [ Box 3 ] [ Box 4 ]
  0x100     0x104     0x108     0x10C     0x110

Original:  ["C", "A", "T"]  (Frozen in memory)
Mutation:  s[1] = "O"       ❌ ILLEGAL!
Remelted:  ["C", "O", "T"]  ✅ Allocated as a brand new block elsewhere

# 1. In-place Reverse (Two Pointers) — O(N) Time, O(1) Space
def reverse_array(arr: list[int]) -> None:
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# 2. In-place Compaction (Remove Duplicates from Sorted Array)
def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    write_idx = 1
    for read_idx in range(1, len(nums)):
        if nums[read_idx] != nums[read_idx - 1]:
            nums[write_idx] = nums[read_idx]
            write_idx += 1
    return write_idx  # Length of unique prefix

# 3. Running Prefix Sums — Enables O(1) Subarray Sum Queries
def build_prefix_sums(nums: list[int]) -> list[int]:
    pref = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        pref[i + 1] = pref[i] + x
    return pref  # Subarray sum nums[L..R] = pref[R + 1] - pref[L]

# 4. Fast String Building — O(N) Time (NEVER use `s += char` in loops!)
def build_string_fast(n: int) -> str:
    chunks: list[str] = []
    for i in range(n):
        chunks.append(str(i))
    return "".join(chunks)  # Single O(N) allocation instead of O(N^2) quadratic churn

Array (Contiguous):
[ L1 Cache Hit | L1 Cache Hit | L1 Cache Hit | L1 Cache Hit ]  ⚡ ~1ns

Linked List (Scattered Pointers):
[ Cache Miss → Wait 100ns ] ──> [ Cache Miss → Wait 100ns ]    🐌 ~100ns

"""
Production Dynamic Array Implementation from Scratch.
Demonstrates geometric over-allocation, bounds verification, and amortized resizing.
"""

from typing import Any, Iterator, Optional

class DynamicArray:
    """A resilient, dynamically resizing array similar to Python list or C++ std::vector."""

    INITIAL_CAPACITY: int = 4
    GROWTH_FACTOR: int = 2

    def __init__(self, initial_capacity: Optional[int] = None) -> None:
        self._capacity: int = initial_capacity if initial_capacity else self.INITIAL_CAPACITY
        self._size: int = 0
        self._buffer: list[Any] = [None] * self._capacity

    def __len__(self) -> int:
        return self._size

    def __getitem__(self, index: int) -> Any:
        self._validate_index(index)
        return self._buffer[index]

    def __setitem__(self, index: int, value: Any) -> None:
        self._validate_index(index)
        self._buffer[index] = value

    def append(self, item: Any) -> None:
        """Appends item to the end in amortized O(1) time."""
        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        self._buffer[self._size] = item
        self._size += 1

    def pop(self) -> Any:
        """Removes and returns the last element in O(1) time."""
        if self._size == 0:
            raise IndexError("pop from empty dynamic array")
        self._size -= 1
        val = self._buffer[self._size]
        self._buffer[self._size] = None  # Prevent memory leak

        # Optional shrink to preserve memory footprint
        if 0 < self._size <= self._capacity // 4:
            self._resize(max(self.INITIAL_CAPACITY, self._capacity // 2))
        return val

    def insert(self, index: int, item: Any) -> None:
        """Inserts an element at an arbitrary index in O(N) time."""
        if not (0 <= index <= self._size):
            raise IndexError(f"Insert index {index} out of bounds for size {self._size}")
        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)

        # Shift elements right to create a slot
        for i in range(self._size, index, -1):
            self._buffer[i] = self._buffer[i - 1]

        self._buffer[index] = item
        self._size += 1

    def _resize(self, new_capacity: int) -> None:
        """Allocates a new buffer and migrates elements in O(N) time."""
        new_buffer: list[Any] = [None] * new_capacity
        for i in range(self._size):
            new_buffer[i] = self._buffer[i]
        self._buffer = new_buffer
        self._capacity = new_capacity

    def _validate_index(self, index: int) -> None:
        if not (0 <= index < self._size):
            raise IndexError(f"Index {index} out of bounds for size {self._size}")

    def __iter__(self) -> Iterator[Any]:
        for i in range(self._size):
            yield self._buffer[i]

    def __repr__(self) -> str:
        items = [repr(self._buffer[i]) for i in range(self._size)]
        return f"DynamicArray([{', '.join(items)}], size={self._size}, capacity={self._capacity})"

# ❌ BUG: O(N^2) runtime. Every iteration re-copies the whole string so far!
   s = ""
   for char in huge_stream:
       s += char

   # ✅ FIX: Amortized O(N) total runtime
   buf = []
   for char in huge_stream:
       buf.append(char)
   s = "".join(buf)

from typing import Any, Iterator, Optional


class DynamicArray:
    """A resilient, dynamically resizing array similar to Python list or C++ std::vector.

    Complexity:
        - Access: O(1)
        - Update: O(1)
        - Append: Amortized O(1), Worst-case O(N) on resize
        - Pop: O(1)
        - Insert (arbitrary): O(N)
        - Delete (arbitrary): O(N)
        - Space: O(N)
    """

    INITIAL_CAPACITY: int = 4
    GROWTH_FACTOR: int = 2

    def __init__(self, initial_capacity: Optional[int] = None) -> None:
        """Initializes dynamic array with given or default capacity."""
        self._capacity: int = initial_capacity if initial_capacity else self.INITIAL_CAPACITY
        self._size: int = 0
        self._buffer: list[Any] = [None] * self._capacity

    def __len__(self) -> int:
        """Returns the number of active elements in the array."""
        return self._size

    @property
    def capacity(self) -> int:
        """Returns the current internal buffer capacity."""
        return self._capacity

    def is_empty(self) -> bool:
        """Returns True if the array contains zero elements."""
        return self._size == 0

    def __getitem__(self, index: int) -> Any:
        """Retrieves an element at the specified index."""
        actual_index = self._normalize_index(index)
        return self._buffer[actual_index]

    def __setitem__(self, index: int, value: Any) -> None:
        """Assigns a value to the specified index."""
        actual_index = self._normalize_index(index)
        self._buffer[actual_index] = value

    def append(self, item: Any) -> None:
        """Appends an item to the end of the array in amortized O(1) time."""
        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)
        self._buffer[self._size] = item
        self._size += 1

    def pop(self) -> Any:
        """Removes and returns the last element in O(1) time."""
        if self._size == 0:
            raise IndexError("pop from empty dynamic array")
        self._size -= 1
        val = self._buffer[self._size]
        self._buffer[self._size] = None  # Prevent lingering memory references

        # Quarter-capacity shrink threshold to avoid resizing thrash
        if 0 < self._size <= self._capacity // 4 and self._capacity > self.INITIAL_CAPACITY:
            self._resize(max(self.INITIAL_CAPACITY, self._capacity // 2))
        return val

    def insert(self, index: int, item: Any) -> None:
        """Inserts an element at an arbitrary index in O(N) time."""
        if index < 0:
            index += self._size
        if not (0 <= index <= self._size):
            raise IndexError(f"Insert index {index} out of bounds for size {self._size}")

        if self._size == self._capacity:
            self._resize(self._capacity * self.GROWTH_FACTOR)

        for i in range(self._size, index, -1):
            self._buffer[i] = self._buffer[i - 1]

        self._buffer[index] = item
        self._size += 1

    def delete(self, index: int) -> Any:
        """Deletes and returns the element at the specified index in O(N) time."""
        actual_index = self._normalize_index(index)
        removed_val = self._buffer[actual_index]

        for i in range(actual_index, self._size - 1):
            self._buffer[i] = self._buffer[i + 1]

        self._size -= 1
        self._buffer[self._size] = None

        if 0 < self._size <= self._capacity // 4 and self._capacity > self.INITIAL_CAPACITY:
            self._resize(max(self.INITIAL_CAPACITY, self._capacity // 2))

        return removed_val

    def _resize(self, new_capacity: int) -> None:
        """Allocates a new buffer of specified capacity and copies existing items."""
        new_buffer: list[Any] = [None] * new_capacity
        for i in range(self._size):
            new_buffer[i] = self._buffer[i]
        self._buffer = new_buffer
        self._capacity = new_capacity

    def _normalize_index(self, index: int) -> int:
        """Handles negative indexing and raises IndexError for out-of-bounds access."""
        actual_index = index if index >= 0 else index + self._size
        if not (0 <= actual_index < self._size):
            raise IndexError(f"Index {index} out of bounds for array of size {self._size}")
        return actual_index

    def __iter__(self) -> Iterator[Any]:
        """Provides sequential iteration over elements."""
        for i in range(self._size):
            yield self._buffer[i]

    def __repr__(self) -> str:
        """String representation of the dynamic array."""
        elements = [repr(self._buffer[i]) for i in range(self._size)]
        return f"DynamicArray([{', '.join(elements)}], size={self._size}, capacity={self._capacity})"


def test_dynamic_array() -> None:
    """Unit tests verifying DynamicArray behavior under edge cases."""
    arr = DynamicArray(initial_capacity=2)
    assert len(arr) == 0
    assert arr.is_empty()

    # Append tests and resizing
    arr.append(10)
    arr.append(20)
    assert len(arr) == 2
    assert arr.capacity == 2

    # Trigger geometric resize
    arr.append(30)
    assert len(arr) == 3
    assert arr.capacity == 4
    assert arr[0] == 10
    assert arr[1] == 20
    assert arr[2] == 30
    assert arr[-1] == 30

    # Insert test
    arr.insert(1, 15)
    assert list(arr) == [10, 15, 20, 30]

    # Pop test
    popped = arr.pop()
    assert popped == 30
    assert list(arr) == [10, 15, 20]

    # Delete test
    deleted = arr.delete(1)
    assert deleted == 15
    assert list(arr) == [10, 20]

    print("✅ All DynamicArray tests passed successfully!")


if __name__ == "__main__":
    test_dynamic_array()

Your Name: "Alice Smith"
Valet Math: Valet runs Alice's name through a quick magic formula → Ticket #42
Your Coat: Placed onto Hook #42

Key ("Alice")  ──[ Hash Function ]──> Index 42 ──> Bucket[42] = Coat
Key ("Bob")    ──[ Hash Function ]──> Index 87 ──> Bucket[87] = Coat

# 1. Frequency Counter — O(N) Time, O(U) Space (U = unique items)
from collections import Counter, defaultdict

def count_frequencies(words: list[str]) -> dict[str, int]:
    freq: dict[str, int] = defaultdict(int)
    for w in words:
        freq[w] += 1
    return freq

# 2. Two Sum Complement Pattern — O(N) Time, O(N) Space
def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # val -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# 3. Anagram Signature Grouping — O(N * K log K) Time
def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))  # Canonical signature
        groups[key].append(s)
    return list(groups.values())

# 4. LRU Cache Integration via OrderedDict / Hash + DLL
from collections import OrderedDict
lru = OrderedDict()
lru["a"] = 1
lru.move_to_end("a")  # Marked as most recently used in O(1)

Entries Table (Dense, preserves insertion order):
Index 0: [hash("tim"), "tim", 99]
Index 1: [hash("amy"), "amy", 42]

Hash Indices (Sparse, 8 slots):
[ -1, 0, -1, -1, 1, -1, -1, -1 ]
       ↑           ↑
     "tim"       "amy"

"""
Production Hash Table Implementation using Separate Chaining.
Demonstrates load factor monitoring, geometric rehashing, and full mapping protocol.
"""

from typing import Any, Iterator, Optional

class HashNode:
    """A key-value pair node in a collision chain."""
    __slots__ = ("key", "value", "next")

    def __init__(self, key: Any, value: Any, next_node: Optional["HashNode"] = None) -> None:
        self.key: Any = key
        self.value: Any = value
        self.next: Optional[HashNode] = next_node


class HashTable:
    """A resilient, dynamically resizing hash map with separate chaining.

    Complexity:
        - Get: Average O(1), Worst O(N)
        - Put: Average O(1), Worst O(N) on resize
        - Delete: Average O(1), Worst O(N)
        - Space: O(N + M) where M is bucket count
    """

    INITIAL_BUCKETS: int = 16
    MAX_LOAD_FACTOR: float = 0.75

    def __init__(self, capacity: Optional[int] = None) -> None:
        self._capacity: int = capacity if capacity else self.INITIAL_BUCKETS
        self._size: int = 0
        self._buckets: list[Optional[HashNode]] = [None] * self._capacity

    def __len__(self) -> int:
        return self._size

    @property
    def load_factor(self) -> float:
        """Returns alpha = N / M."""
        return self._size / self._capacity

    def _hash(self, key: Any) -> int:
        """Computes bucket index using Python's built-in hash with bit masking."""
        return (hash(key) & 0x7FFFFFFF) % self._capacity

    def __setitem__(self, key: Any, value: Any) -> None:
        """Inserts or updates a key-value pair in average O(1) time."""
        index = self._hash(key)
        head = self._buckets[index]

        # Scan chain for existing key
        curr = head
        while curr:
            if curr.key == key:
                curr.value = value
                return
            curr = curr.next

        # Insert new node at head of chain
        new_node = HashNode(key, value, head)
        self._buckets[index] = new_node
        self._size += 1

        # Check resize threshold
        if self.load_factor > self.MAX_LOAD_FACTOR:
            self._rehash(self._capacity * 2)

    def __getitem__(self, key: Any) -> Any:
        """Retrieves value associated with key, raising KeyError if absent."""
        index = self._hash(key)
        curr = self._buckets[index]
        while curr:
            if curr.key == key:
                return curr.value
            curr = curr.next
        raise KeyError(f"Key '{key}' not found in hash table")

    def __delitem__(self, key: Any) -> None:
        """Deletes key-value pair in average O(1) time."""
        index = self._hash(key)
        curr = self._buckets[index]
        prev: Optional[HashNode] = None

        while curr:
            if curr.key == key:
                if prev:
                    prev.next = curr.next
                else:
                    self._buckets[index] = curr.next
                self._size -= 1
                return
            prev = curr
            curr = curr.next

        raise KeyError(f"Key '{key}' not found for deletion")

    def __contains__(self, key: Any) -> bool:
        try:
            self.__getitem__(key)
            return True
        except KeyError:
            return False

    def _rehash(self, new_capacity: int) -> None:
        """Re-allocates bucket array and migrates all existing nodes."""
        old_buckets = self._buckets
        self._capacity = new_capacity
        self._buckets = [None] * self._capacity
        self._size = 0  # Re-counted during re-insertion

        for head in old_buckets:
            curr = head
            while curr:
                self.__setitem__(curr.key, curr.value)
                curr = curr.next

    def __iter__(self) -> Iterator[Any]:
        """Iterates over all stored keys."""
        for head in self._buckets:
            curr = head
            while curr:
                yield curr.key
                curr = curr.next

# ❌ ILLEGAL: TypeError: unhashable type: 'list'
   d = {}
   d[[1, 2]] = "error"

   # ✅ FIX: Convert to immutable tuple
   d[(1, 2)] = "success"

from typing import Any, Iterator, Optional, Tuple


class HashNode:
    """A single key-value node within a collision chain."""

    __slots__ = ("key", "value", "next")

    def __init__(self, key: Any, value: Any, next_node: Optional["HashNode"] = None) -> None:
        self.key: Any = key
        self.value: Any = value
        self.next: Optional[HashNode] = next_node


class HashTable:
    """A resilient, dynamically resizing hash map using separate chaining.

    Complexity:
        - Access: Average O(1), Worst O(N)
        - Insert/Update: Average O(1), Worst O(N) on resize
        - Delete: Average O(1), Worst O(N)
        - Space: O(N + M) where M is bucket capacity
    """

    INITIAL_CAPACITY: int = 16
    MAX_LOAD_FACTOR: float = 0.75

    def __init__(self, capacity: Optional[int] = None) -> None:
        """Initializes hash table with given capacity or default 16 buckets."""
        self._capacity: int = capacity if capacity else self.INITIAL_CAPACITY
        self._size: int = 0
        self._buckets: list[Optional[HashNode]] = [None] * self._capacity

    def __len__(self) -> int:
        """Returns the number of active key-value pairs."""
        return self._size

    @property
    def capacity(self) -> int:
        """Returns the number of internal buckets."""
        return self._capacity

    @property
    def load_factor(self) -> float:
        """Returns the current load factor alpha = N / M."""
        return self._size / self._capacity

    def _hash(self, key: Any) -> int:
        """Computes internal bucket index using positive 31-bit modulo."""
        return (hash(key) & 0x7FFFFFFF) % self._capacity

    def __setitem__(self, key: Any, value: Any) -> None:
        """Inserts or updates a key-value pair in average O(1) time."""
        index = self._hash(key)
        head = self._buckets[index]

        # Scan for existing key in bucket chain
        curr = head
        while curr:
            if curr.key == key:
                curr.value = value
                return
            curr = curr.next

        # Insert new node at head of chain
        new_node = HashNode(key, value, head)
        self._buckets[index] = new_node
        self._size += 1

        # Check if resize threshold exceeded
        if self.load_factor > self.MAX_LOAD_FACTOR:
            self._rehash(self._capacity * 2)

    def __getitem__(self, key: Any) -> Any:
        """Retrieves value associated with key, raising KeyError if absent."""
        index = self._hash(key)
        curr = self._buckets[index]
        while curr:
            if curr.key == key:
                return curr.value
            curr = curr.next
        raise KeyError(f"Key '{key}' not found in hash table")

    def __delitem__(self, key: Any) -> None:
        """Deletes key-value pair in average O(1) time."""
        index = self._hash(key)
        curr = self._buckets[index]
        prev: Optional[HashNode] = None

        while curr:
            if curr.key == key:
                if prev:
                    prev.next = curr.next
                else:
                    self._buckets[index] = curr.next
                self._size -= 1
                return
            prev = curr
            curr = curr.next

        raise KeyError(f"Key '{key}' not found for deletion")

    def __contains__(self, key: Any) -> bool:
        """Checks if key exists in table."""
        try:
            self.__getitem__(key)
            return True
        except KeyError:
            return False

    def get(self, key: Any, default: Any = None) -> Any:
        """Retrieves value or default fallback."""
        try:
            return self.__getitem__(key)
        except KeyError:
            return default

    def _rehash(self, new_capacity: int) -> None:
        """Re-allocates bucket table and migrates all existing nodes."""
        old_buckets = self._buckets
        self._capacity = new_capacity
        self._buckets = [None] * self._capacity
        self._size = 0  # Re-tallied via __setitem__

        for head in old_buckets:
            curr = head
            while curr:
                self.__setitem__(curr.key, curr.value)
                curr = curr.next

    def items(self) -> Iterator[Tuple[Any, Any]]:
        """Yields (key, value) pairs."""
        for head in self._buckets:
            curr = head
            while curr:
                yield (curr.key, curr.value)
                curr = curr.next

    def keys(self) -> Iterator[Any]:
        """Yields keys."""
        for k, _ in self.items():
            yield k

    def values(self) -> Iterator[Any]:
        """Yields values."""
        for _, v in self.items():
            yield v

    def __iter__(self) -> Iterator[Any]:
        """Default iteration over keys."""
        return self.keys()

    def __repr__(self) -> str:
        """Visual representation of key-value pairs."""
        pairs = [f"{repr(k)}: {repr(v)}" for k, v in self.items()]
        return f"HashTable({{{', '.join(pairs)}}}, size={self._size}, capacity={self._capacity})"


def test_hash_table() -> None:
    """Unit tests verifying HashTable correctness and collision handling."""
    ht = HashTable(capacity=4)
    assert len(ht) == 0
    assert ht.capacity == 4

    # Insert elements
    ht["apple"] = 100
    ht["banana"] = 200
    ht["cherry"] = 300
    assert len(ht) == 3
    assert ht["apple"] == 100
    assert ht["banana"] == 200
    assert ht["cherry"] == 300

    # Overwrite existing key
    ht["banana"] = 250
    assert ht["banana"] == 250
    assert len(ht) == 3

    # Trigger rehash (load factor > 0.75: 4 items in 4 buckets = 1.0 > 0.75)
    ht["date"] = 400
    assert len(ht) == 4
    assert ht.capacity == 8  # Doubled!
    assert ht["apple"] == 100
    assert ht["date"] == 400

    # Test membership
    assert "apple" in ht
    assert "grape" not in ht
    assert ht.get("grape", 999) == 999

    # Test deletion
    del ht["banana"]
    assert len(ht) == 3
    assert "banana" not in ht

    print("✅ All HashTable tests passed successfully!")


if __name__ == "__main__":
    test_hash_table()

[ Outer Doll (N) ]
  └── [ Inside Doll (N-1) ]
        └── [ Inside Doll (N-2) ]
              └── [ Solid Wood Core (Base Case) ] 🛑

# Archetype 1: Linear Recursion (Single Branch) — e.g. Binary Search
# Time: O(log N), Space: O(log N) stack frames
def binary_search(arr: list[int], target: int, low: int, high: int) -> int:
    if low > high:
        return -1  # Base Case 1: Exhausted
    mid = low + (high - low) // 2
    if arr[mid] == target:
        return mid  # Base Case 2: Found
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)  # Recurse left
    else:
        return binary_search(arr, target, mid + 1, high)  # Recurse right


# Archetype 2: Binary Branching (Divide & Conquer) — e.g. Tree Height
# Time: O(N), Space: O(Height) stack frames
def max_depth(node) -> int:
    if not node:
        return 0  # Base Case: Empty tree has height 0
    left_h = max_depth(node.left)
    right_h = max_depth(node.right)
    return 1 + max(left_h, right_h)  # Combine step


# Archetype 3: Multi-Branching Backtracking — e.g. Generate Subsets
# Time: O(2^N), Space: O(N) max depth
def generate_subsets(nums: list[int]) -> list[list[int]]:
    results: list[list[int]] = []
    subset: list[int] = []

    def dfs(idx: int) -> None:
        if idx == len(nums):
            results.append(list(subset))  # Base Case: Reached leaf
            return
        # Decision 1: Include nums[idx]
        subset.append(nums[idx])
        dfs(idx + 1)
        # Backtrack (Undo decision)
        subset.pop()
        # Decision 2: Exclude nums[idx]
        dfs(idx + 1)

    dfs(0)
    return results

"""
Demonstrating Recursive DFS vs Explicit Heap Stack Simulation.
"""

from typing import Optional

class TreeNode:
    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def inorder_traversal_iterative(root: Optional[TreeNode]) -> list[int]:
    """Iterative In-order traversal using an explicit list as the call stack.

    Time: O(N)
    Space: O(H) on the heap — immune to Python RecursionError!
    """
    result: list[int] = []
    stack: list[TreeNode] = []
    curr = root

    while curr or stack:
        # Push all left children onto stack (simulating downward recursion)
        while curr:
            stack.append(curr)
            curr = curr.left

        # Pop from stack (simulating return from child recursion)
        curr = stack.pop()
        result.append(curr.val)

        # Move to right subtree
        curr = curr.right

    return result

# ❌ BUG: Appends reference to same list; ending with [ [], [], [] ]
   results.append(path)

   # ✅ FIX: Create shallow copy snapshot
   results.append(list(path))  # or path[:]

CALL _child_function    ; Pushes Return Address to Stack
...
RET                     ; Pops Return Address

def tail_factorial(n: int, accumulator: int = 1) -> int:
    if n <= 1:
        return accumulator
    return tail_factorial(n - 1, n * accumulator)  # Pure tail call

MOV rdi, rax            ; Update accumulator
SUB rsi, 1              ; Decrement n
JMP _tail_factorial     ; Reuse identical stack frame!

# The Y Combinator in Python: Enables recursive factorial without named recursion!
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))

# Define factorial without referencing its own name
factorial_logic = lambda rec: lambda n: 1 if n <= 1 else n * rec(n - 1)

anonymous_factorial = Y(factorial_logic)
assert anonymous_factorial(5) == 120  # Works purely through lambda calculus!

from typing import Any, List, Optional


class TreeNode:
    """Standard binary tree node."""

    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def merge_sort(nums: List[int]) -> List[int]:
    """Classic Divide-and-Conquer Sort.

    Recurrence: T(N) = 2T(N/2) + O(N) -> O(N log N) time, O(N) space.
    """
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])

    # Combine step
    merged: List[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def inorder_recursive(root: Optional[TreeNode]) -> List[int]:
    """Standard recursive DFS traversal."""
    result: List[int] = []

    def dfs(node: Optional[TreeNode]) -> None:
        if not node:
            return
        dfs(node.left)
        result.append(node.val)
        dfs(node.right)

    dfs(root)
    return result


def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
    """Iterative in-order traversal using an explicit list as call stack."""
    result: List[int] = []
    stack: List[TreeNode] = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right

    return result


def generate_subsets(nums: List[int]) -> List[List[int]]:
    """Backtracking pattern exploring a binary state-space decision tree.

    Time: O(2^N), Space: O(N) auxiliary recursion stack.
    """
    results: List[List[int]] = []
    subset: List[int] = []

    def backtrack(idx: int) -> None:
        if idx == len(nums):
            results.append(list(subset))
            return

        # Decision 1: Pick nums[idx]
        subset.append(nums[idx])
        backtrack(idx + 1)

        # Undo decision
        subset.pop()

        # Decision 2: Do NOT pick nums[idx]
        backtrack(idx + 1)

    backtrack(0)
    return results


def tail_factorial(n: int, accumulator: int = 1) -> int:
    """Tail-recursive factorial with accumulator."""
    if n <= 1:
        return accumulator
    return tail_factorial(n - 1, n * accumulator)


def test_recursion_patterns() -> None:
    """Unit tests verifying recursive implementations."""
    # 1. Merge Sort test
    nums = [38, 27, 43, 3, 9, 82, 10]
    sorted_nums = merge_sort(nums)
    assert sorted_nums == [3, 9, 10, 27, 38, 43, 82]

    # 2. Tree Traversal (Recursive vs Iterative)
    # Tree:   1
    #        / \
    #       2   3
    #      / \
    #     4   5
    root = TreeNode(1)
    root.left = TreeNode(2, TreeNode(4), TreeNode(5))
    root.right = TreeNode(3)

    rec_result = inorder_recursive(root)
    iter_result = inorder_iterative(root)
    assert rec_result == [4, 2, 5, 1, 3]
    assert iter_result == [4, 2, 5, 1, 3]

    # 3. Subsets Backtracking
    subsets = generate_subsets([1, 2])
    assert len(subsets) == 4
    assert [1, 2] in subsets
    assert [1] in subsets
    assert [2] in subsets
    assert [] in subsets

    # 4. Tail Factorial
    assert tail_factorial(5) == 120
    assert tail_factorial(0) == 1

    print("✅ All Recursion pattern tests passed successfully!")


if __name__ == "__main__":
    test_recursion_patterns()

Teacher picks one child as the "Pivot".
  "Everyone shorter than the Pivot, go to the left fence!"
  "Everyone taller than the Pivot, go to the right fence!"
  Now repeat the same game within the left and right groups.

# 1. 3-Way QuickSort (Dutch National Flag Partitioning)
# Immune to O(N^2) duplicates degradation!
import random

def quicksort_3way(arr: list[int], low: int, high: int) -> None:
    if low >= high:
        return
    # Random pivot to eliminate sorted array worst-case
    p_idx = random.randint(low, high)
    arr[low], arr[p_idx] = arr[p_idx], arr[low]
    pivot = arr[low]

    lt, i, gt = low, low + 1, high
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1

    quicksort_3way(arr, low, lt - 1)
    quicksort_3way(arr, gt + 1, high)


# 2. Counting Sort — O(N + K) Non-comparison sorting
def counting_sort(nums: list[int]) -> list[int]:
    if not nums:
        return []
    min_val, max_val = min(nums), max(nums)
    k = max_val - min_val + 1
    counts = [0] * k

    for x in nums:
        counts[x - min_val] += 1

    sorted_res: list[int] = []
    for val_offset, count in enumerate(counts):
        sorted_res.extend([val_offset + min_val] * count)
    return sorted_res

"""
Production-Grade In-Place Heap Sort.
Achieves O(N log N) time and strict O(1) auxiliary space without external arrays.
"""

def heapsort(arr: list[int]) -> None:
    """Sorts arr in-place in ascending order using a Max-Heap.

    Time Complexity:
        - Build Max-Heap: O(N) via Floyd's bottom-up sift-down
        - N Extractions: N * O(log N) = O(N log N)
        - Total Time: O(N log N)
    Space Complexity:
        - O(1) strictly in-place.
    """
    n = len(arr)

    def sift_down(start: int, end: int) -> None:
        root = start
        while True:
            child = 2 * root + 1  # Left child index
            if child > end:
                break
            # Pick largest child
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child  # Continue down
            else:
                break

    # Phase 1: Build Max-Heap in O(N) time bottom-up
    for i in range((n - 2) // 2, -1, -1):
        sift_down(i, n - 1)

    # Phase 2: Extract elements one by one from heap to back of array
    for end in range(n - 1, 0, -1):
        # Swap current max (at index 0) to its final position at 'end'
        arr[0], arr[end] = arr[end], arr[0]
        # Re-heapify remaining elements [0 ... end - 1]
        sift_down(0, end - 1)

import random
from typing import List


def quicksort_3way(arr: List[int]) -> List[int]:
    """Sorts array using 3-Way QuickSort with randomized pivot selection.

    Time Complexity:
        - Best: O(N log N)
        - Average: O(N log N)
        - Worst: O(N log N) expected with random pivot; O(N) if all duplicate values.
    Space Complexity:
        - O(log N) auxiliary recursion call stack.
    """
    copy_arr = list(arr)

    def _sort(low: int, high: int) -> None:
        if low >= high:
            return
        p_idx = random.randint(low, high)
        copy_arr[low], copy_arr[p_idx] = copy_arr[p_idx], copy_arr[low]
        pivot = copy_arr[low]

        lt, i, gt = low, low + 1, high
        while i <= gt:
            if copy_arr[i] < pivot:
                copy_arr[lt], copy_arr[i] = copy_arr[i], copy_arr[lt]
                lt += 1
                i += 1
            elif copy_arr[i] > pivot:
                copy_arr[i], copy_arr[gt] = copy_arr[gt], copy_arr[i]
                gt -= 1
            else:
                i += 1

        _sort(low, lt - 1)
        _sort(gt + 1, high)

    _sort(0, len(copy_arr) - 1)
    return copy_arr


def heapsort(arr: List[int]) -> List[int]:
    """Sorts array in-place using Max-Heap Floyd bottom-up sift-down.

    Time Complexity: O(N log N) guaranteed in all cases.
    Space Complexity: O(1) auxiliary space.
    """
    copy_arr = list(arr)
    n = len(copy_arr)

    def sift_down(start: int, end: int) -> None:
        root = start
        while True:
            child = 2 * root + 1
            if child > end:
                break
            if child + 1 <= end and copy_arr[child] < copy_arr[child + 1]:
                child += 1
            if copy_arr[root] < copy_arr[child]:
                copy_arr[root], copy_arr[child] = copy_arr[child], copy_arr[root]
                root = child
            else:
                break

    # Build heap bottom-up
    for i in range((n - 2) // 2, -1, -1):
        sift_down(i, n - 1)

    # Extract max elements to the end
    for end in range(n - 1, 0, -1):
        copy_arr[0], copy_arr[end] = copy_arr[end], copy_arr[0]
        sift_down(0, end - 1)

    return copy_arr


def counting_sort(nums: List[int]) -> List[int]:
    """Non-comparison sort for integers within arbitrary bounded range.

    Time Complexity: O(N + K) where K = max - min + 1.
    Space Complexity: O(K) for count table.
    """
    if not nums:
        return []
    min_val, max_val = min(nums), max(nums)
    k = max_val - min_val + 1
    counts = [0] * k

    for x in nums:
        counts[x - min_val] += 1

    sorted_res: List[int] = []
    for val_offset, count in enumerate(counts):
        sorted_res.extend([val_offset + min_val] * count)

    return sorted_res


def test_sorting_algorithms() -> None:
    """Unit tests verifying all sorting algorithms against edge cases."""
    test_cases = [
        [],
        [1],
        [5, 4, 3, 2, 1],
        [1, 2, 3, 4, 5],
        [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5],
        [-10, 5, -3, 0, 100, -50, 42],
        [7, 7, 7, 7, 7, 7],
    ]

    for tc in test_cases:
        expected = sorted(tc)
        assert quicksort_3way(tc) == expected, f"QuickSort failed on {tc}"
        assert heapsort(tc) == expected, f"HeapSort failed on {tc}"
        assert counting_sort(tc) == expected, f"CountingSort failed on {tc}"

    print("✅ All Sorting Algorithm tests passed successfully!")


if __name__ == "__main__":
    test_sorting_algorithms()

Push(C) ──>  [ Tray C ]  (Top)  ──> Pop() returns C
             [ Tray B ]
             [ Tray A ]  (Bottom)

Enqueue("Bob") ──> [ Back: Bob ] ──> [ Front: Alice ] ──> Dequeue() returns Alice

from collections import deque

# 1. Valid Parentheses Matching (Stack Pattern)
def is_valid_parentheses(s: str) -> bool:
    bracket_map = {")": "(", "}": "{", "]": "["}
    stack: list[str] = []
    for char in s:
        if char in bracket_map:
            top = stack.pop() if stack else "#"
            if bracket_map[char] != top:
                return False
        else:
            stack.append(char)
    return len(stack) == 0


# 2. BFS Level-Order Traversal (Queue Pattern)
def bfs_levels(root) -> list[list[int]]:
    if not root:
        return []
    result: list[list[int]] = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level: list[int] = []
        for _ in range(level_size):
            node = queue.popleft()  # O(1) dequeue!
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result


# 3. Monotonic Decreasing Stack (Next Greater Element)
def next_greater_elements(nums: list[int]) -> list[int]:
    res = [-1] * len(nums)
    stack: list[int] = []  # Stores indices
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            prev_idx = stack.pop()
            res[prev_idx] = x
        stack.append(i)
    return res

"""
Production Fixed-Capacity Ring Buffer Queue.
Guarantees zero memory allocation after initialization, zero pointer overhead, and O(1) ops.
"""

from typing import Any, Optional

class CircularQueue:
    """A high-performance circular ring buffer queue."""

    def __init__(self, capacity: int) -> None:
        self._capacity: int = capacity
        self._buffer: list[Any] = [None] * capacity
        self._head: int = 0
        self._tail: int = 0
        self._size: int = 0

    def is_empty(self) -> bool:
        return self._size == 0

    def is_full(self) -> bool:
        return self._size == self._capacity

    def enqueue(self, item: Any) -> bool:
        """Enqueues item at tail in O(1) time. Returns False if full."""
        if self.is_full():
            return False
        self._buffer[self._tail] = item
        self._tail = (self._tail + 1) % self._capacity
        self._size += 1
        return True

    def dequeue(self) -> Optional[Any]:
        """Dequeues item from head in O(1) time. Returns None if empty."""
        if self.is_empty():
            return None
        val = self._buffer[self._head]
        self._buffer[self._head] = None  # GC cleanup
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return val

    def peek(self) -> Optional[Any]:
        return None if self.is_empty() else self._buffer[self._head]

    def __len__(self) -> int:
        return self._size

Single Node (Pointers): [Node] ──cache miss──> [Node] ──cache miss──> [Node]
Chunked (Python deque): [ 64 Contiguous Elements ] ──> [ 64 Contiguous Elements ]

from typing import Optional, Any
import collections.abc

class Node[T]:
    """Singly linked node for Stack and Queue."""
    __slots__ = ("val", "next")
    def __init__(self, val: T, next_node: Optional['Node[T]'] = None):
        self.val = val
        self.next = next_node
    def __repr__(self) -> str:
        return f"Node({self.val})"


class Stack[T]:
    """LIFO Data Structure using a Singly Linked List (Head pointer only)."""
    __slots__ = ("_head", "_size")

    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    def __len__(self) -> int:
        return self._size

    def push(self, val: T) -> None:
        """Adds an item to the top of the stack. O(1) time."""
        self._head = Node(val, self._head)
        self._size += 1

    def pop(self) -> T:
        """Removes and returns the top item. O(1) time."""
        if self.is_empty:
            raise IndexError("pop from empty Stack")
        val = self._head.val
        self._head = self._head.next
        self._size -= 1
        return val

    def peek(self) -> T:
        """Returns the top item without removing it. O(1) time."""
        if self.is_empty:
            raise IndexError("peek from empty Stack")
        return self._head.val
        
    def __repr__(self) -> str:
        curr = self._head
        vals = []
        while curr:
            vals.append(str(curr.val))
            curr = curr.next
        return f"Stack(Top -> [{', '.join(vals)}])"


class Queue[T]:
    """FIFO Data Structure using a Singly Linked List (Head and Tail pointers)."""
    __slots__ = ("_head", "_tail", "_size")

    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    def __len__(self) -> int:
        return self._size

    def enqueue(self, val: T) -> None:
        """Adds an item to the back of the queue. O(1) time."""
        new_node = Node(val)
        if self.is_empty:
            self._head = self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1

    def dequeue(self) -> T:
        """Removes and returns the front item. O(1) time."""
        if self.is_empty:
            raise IndexError("dequeue from empty Queue")
        val = self._head.val
        self._head = self._head.next
        self._size -= 1
        if self.is_empty:
            self._tail = None
        return val

    def peek(self) -> T:
        """Returns the front item without removing it. O(1) time."""
        if self.is_empty:
            raise IndexError("peek from empty Queue")
        return self._head.val

    def __repr__(self) -> str:
        curr = self._head
        vals = []
        while curr:
            vals.append(str(curr.val))
            curr = curr.next
        return f"Queue(Front -> [{', '.join(vals)}] <- Back)"


if __name__ == "__main__":
    print("Testing Stack (LIFO)...")
    stack: Stack[int] = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    assert str(stack) == "Stack(Top -> [3, 2, 1])"
    assert stack.peek() == 3
    assert stack.pop() == 3
    assert stack.pop() == 2
    assert len(stack) == 1
    assert stack.pop() == 1
    assert stack.is_empty
    print("✅ Stack tests passed!")

    print("\nTesting Queue (FIFO)...")
    queue: Queue[str] = Queue()
    queue.enqueue("Alice")
    queue.enqueue("Bob")
    queue.enqueue("Charlie")
    assert str(queue) == "Queue(Front -> [Alice, Bob, Charlie] <- Back)"
    assert queue.peek() == "Alice"
    assert queue.dequeue() == "Alice"
    assert queue.dequeue() == "Bob"
    assert len(queue) == 1
    assert queue.dequeue() == "Charlie"
    assert queue.is_empty
    print("✅ Queue tests passed!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

[ Head: Park ] ──next──> [ Grand Central ] ──next──> [ Brooklyn Bridge ] ──next──> None

# 1. In-Place Reversal — O(N) Time, O(1) Space
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next     # 1. Save forward pointer
        curr.next = prev    # 2. Reverse link
        prev = curr         # 3. Advance prev
        curr = nxt          # 4. Advance curr
    return prev  # New head!


# 2. Fast & Slow Pointers (Midpoint & Cycle Detection)
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 1 step
        fast = fast.next.next     # 2 steps
    return slow  # Exact midpoint!


# 3. Sentinel Node Deletion (Remove All Nodes Matching Val)
def remove_elements(head, val: int):
    dummy = ListNode(0, head)
    curr = dummy
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next  # Bypass node
        else:
            curr = curr.next
    return dummy.next

"""
Production Singly Linked List Implementation with __slots__ and Type Hints.
"""

from typing import Any, Iterator, Optional

class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: Any, next_node: Optional["ListNode"] = None) -> None:
        self.val: Any = val
        self.next: Optional[ListNode] = next_node


class LinkedList:
    """A resilient singly linked list with O(1) tail tracking."""

    def __init__(self) -> None:
        self._head: Optional[ListNode] = None
        self._tail: Optional[ListNode] = None
        self._size: int = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def append(self, val: Any) -> None:
        """Appends value to the tail in O(1) time."""
        new_node = ListNode(val)
        if not self._head:
            self._head = self._tail = new_node
        else:
            assert self._tail is not None
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1

    def prepend(self, val: Any) -> None:
        """Prepends value to the head in O(1) time."""
        new_node = ListNode(val, self._head)
        self._head = new_node
        if self._size == 0:
            self._tail = new_node
        self._size += 1

    def pop_front(self) -> Any:
        """Removes and returns head value in O(1) time."""
        if not self._head:
            raise IndexError("pop from empty linked list")
        val = self._head.val
        self._head = self._head.next
        self._size -= 1
        if self._size == 0:
            self._tail = None
        return val

    def reverse(self) -> None:
        """Reverses list in-place in O(N) time and O(1) auxiliary space."""
        prev: Optional[ListNode] = None
        curr = self._head
        self._tail = self._head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self._head = prev

    def __iter__(self) -> Iterator[Any]:
        curr = self._head
        while curr:
            yield curr.val
            curr = curr.next

Level 3: Head ─────────────────────────> Node(17) ─────────────────────────> None
Level 2: Head ───────────> Node(7) ────> Node(17) ───────────> Node(25) ────> None
Level 1: Head ──> Node(3) ──> Node(7) ──> Node(17) ──> Node(19) ──> Node(25) ──> None

from typing import Optional, Any
import collections.abc

class Node[T]:
    """
    A single node in the Linked List.
    Using __slots__ prevents dynamic dictionary creation, saving ~65% memory per node!
    """
    __slots__ = ("val", "next")

    def __init__(self, val: T, next_node: Optional['Node[T]'] = None):
        self.val = val
        self.next = next_node

    def __repr__(self) -> str:
        return f"Node({self.val})"


class LinkedList[T]:
    """
    A highly optimized Singly Linked List.
    Tracks head, tail, and size for maximum efficiency.
    """
    __slots__ = ("_head", "_tail", "_size")

    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    @property
    def head(self) -> Optional[Node[T]]:
        return self._head

    @property
    def tail(self) -> Optional[Node[T]]:
        return self._tail

    def __len__(self) -> int:
        """Enables len(my_list) in O(1) time."""
        return self._size

    def __iter__(self) -> collections.abc.Iterator[T]:
        """Enables for loop traversal: 'for item in my_list:'"""
        curr = self._head
        while curr:
            yield curr.val
            curr = curr.next

    def __repr__(self) -> str:
        """Enables clean printing: 'LinkedList[1 -> 2 -> 3]'"""
        values = " -> ".join(str(val) for val in self)
        return f"LinkedList[{values}]"

    def append(self, val: T) -> 'LinkedList[T]':
        """Adds a node to the END of the list in O(1) time."""
        new_node = Node(val)
        if self.is_empty:
            self._head = self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1
        return self  # Return self for method chaining

    def prepend(self, val: T) -> 'LinkedList[T]':
        """Adds a node to the FRONT of the list in O(1) time."""
        new_node = Node(val, self._head)
        self._head = new_node
        if self.is_empty:
            self._tail = new_node
        self._size += 1
        return self

    def insert_at(self, index: int, val: T) -> 'LinkedList[T]':
        """Inserts a node at a specific index in O(N) time."""
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        match index:
            case 0:
                return self.prepend(val)
            case idx if idx == self._size:
                return self.append(val)
            case _:
                # Traverse to the node JUST BEFORE the insertion point
                curr = self._head
                for _ in range(index - 1):
                    curr = curr.next
                
                new_node = Node(val, curr.next)
                curr.next = new_node
                self._size += 1
                return self

    def delete(self, val: T) -> bool:
        """Deletes the FIRST occurrence of a value. Returns True if deleted, else False. O(N) time."""
        if self.is_empty:
            return False

        if self._head.val == val:
            self._head = self._head.next
            self._size -= 1
            if self.is_empty:
                self._tail = None
            return True

        curr = self._head
        while curr.next:
            if curr.next.val == val:
                if curr.next == self._tail:
                    self._tail = curr  # Update tail if deleting the last node
                curr.next = curr.next.next
                self._size -= 1
                return True
            curr = curr.next

        return False

    def search(self, val: T) -> bool:
        """Searches for a value in the list. O(N) time."""
        return any(curr_val == val for curr_val in self)

    def reverse(self) -> 'LinkedList[T]':
        """Reverses the linked list in-place in O(N) time."""
        prev = None
        curr = self._head
        self._tail = self._head  # The old head becomes the new tail

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        self._head = prev  # The old tail becomes the new head
        return self


if __name__ == "__main__":
    print("Testing highly optimized Python 3.14 LinkedList...")
    
    # 1. Initialization and Appending (Testing Generics and Method Chaining)
    ll: LinkedList[int] = LinkedList()
    ll.append(1).append(2).append(3)
    
    assert len(ll) == 3
    assert ll.head.val == 1
    assert ll.tail.val == 3
    assert str(ll) == "LinkedList[1 -> 2 -> 3]"
    print("✅ Append & Initialization passed!")

    # 2. Prepending
    ll.prepend(0)
    assert len(ll) == 4
    assert ll.head.val == 0
    assert str(ll) == "LinkedList[0 -> 1 -> 2 -> 3]"
    print("✅ Prepend passed!")

    # 3. Insertion (Testing Pattern Matching logic)
    ll.insert_at(2, 99)
    assert str(ll) == "LinkedList[0 -> 1 -> 99 -> 2 -> 3]"
    assert len(ll) == 5
    print("✅ Insert passed!")

    # 4. Deletion
    # Delete middle
    deleted = ll.delete(99)
    assert deleted is True
    assert str(ll) == "LinkedList[0 -> 1 -> 2 -> 3]"
    
    # Delete head
    ll.delete(0)
    assert str(ll) == "LinkedList[1 -> 2 -> 3]"
    assert ll.head.val == 1
    
    # Delete tail
    ll.delete(3)
    assert str(ll) == "LinkedList[1 -> 2]"
    assert ll.tail.val == 2
    assert len(ll) == 2
    print("✅ Delete passed!")

    # 5. Searching (Testing __iter__)
    assert ll.search(2) is True
    assert ll.search(99) is False
    print("✅ Search passed!")

    # 6. Reversal
    ll.append(3).append(4)
    assert str(ll) == "LinkedList[1 -> 2 -> 3 -> 4]"
    ll.reverse()
    assert str(ll) == "LinkedList[4 -> 3 -> 2 -> 1]"
    assert ll.head.val == 4
    assert ll.tail.val == 1
    print("✅ Reverse passed!")
    
    print("🎉 All LinkedList tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Two-Way Train & Handshake Chain
Level 200: Street Fundamentals ────► FAANG cheat card, Sentinel trick, Decision matrix & LRU triage
Level 300: Working Professional ───► Sentinel-bounded DLL, O(1) removal, bidirectional traversal
Level 400: Staff & Senior Arch ────► Cache line penalty, Linux intrusive list_head, LRU composition
Level 500: Researcher's Corner ────► XOR Linked List (A ^ B compression), formal invariant proofs

┌───────┐            ┌───────┐            ┌───────┐
None ◄─┤ Prev  │    ┌──────►│ Prev  │    ┌──────►│ Prev  │
       │ Node1 │    │       │ Node2 │    │       │ Node3 │─► None
       │ Next  ├────┘◄──────┤ Next  ├────┘◄──────┤ Next  │
       └───────┘            └───────┘            └───────┘

[Sentinel Head] <=====> [Node 1] <=====> [Node 2] <=====> [Node 3] <=====> [Sentinel Tail]
  (dummy head)                                                               (dummy tail)

┌────────────────────────┐
                          │   Need O(1) Indexing?  │
                          └───────────┬────────────┘
                                      │
                         YES ─────────┴───────── NO
                          │                       │
                 ┌────────────────┐     ┌──────────────────┐
                 │ Dynamic Array  │     │ Need Bidirect /  │
                 │   or Vector    │     │ O(1) Node Remove?│
                 └────────────────┘     └─────────┬────────┘
                                                  │
                                     YES ─────────┴───────── NO
                                      │                       │
                             ┌────────────────┐     ┌──────────────────┐
                             │ Doubly Linked  │     │ Singly Linked    │
                             │ (e.g. LRU, Q)  │     │ List (low memory)│
                             └────────────────┘     └──────────────────┘

"""
Enterprise-Grade Doubly Linked List with Sentinel Boundaries
Python 3.14 Compatible
"""
from typing import Optional, Generic, TypeVar, Iterator

T = TypeVar("T")

class DLLNode(Generic[T]):
    __slots__ = ("val", "prev", "next")

    def __init__(
        self,
        val: Optional[T] = None,
        prev: Optional["DLLNode[T]"] = None,
        next_node: Optional["DLLNode[T]"] = None,
    ) -> None:
        self.val: Optional[T] = val
        self.prev: Optional["DLLNode[T]"] = prev
        self.next: Optional["DLLNode[T]"] = next_node

    def __repr__(self) -> str:
        return f"DLLNode({self.val})"


class DoublyLinkedList(Generic[T]):
    """
    Doubly Linked List bounded by sentinel dummy nodes.
    Guarantees that self.head and self.tail are never null.
    """
    __slots__ = ("head", "tail", "_size")

    def __init__(self) -> None:
        # Sentinel dummy nodes
        self.head: DLLNode[T] = DLLNode()
        self.tail: DLLNode[T] = DLLNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self._size: int = 0

    def __len__(self) -> int:
        return self._size

    def is_empty__(self) -> bool:
        return self._size == 0

    def append(self, val: T) -> DLLNode[T]:
        """Appends value to the tail of the list in O(1) time."""
        return self._insert_between(val, self.tail.prev, self.tail)

    def prepend(self, val: T) -> DLLNode[T]:
        """Prepends value to the head of the list in O(1) time."""
        return self._insert_between(val, self.head, self.head.next)

    def _insert_between(
        self, val: T, predecessor: DLLNode[T], successor: DLLNode[T]
    ) -> DLLNode[T]:
        """Internal helper: Inserts a new node between two existing adjacent nodes in O(1)."""
        new_node = DLLNode(val=val, prev=predecessor, next_node=successor)
        predecessor.next = new_node
        successor.prev = new_node
        self._size += 1
        return new_node

    def remove_node(self, node: DLLNode[T]) -> T:
        """
        Unlinks a given node in O(1) time.
        Does not require finding the predecessor!
        """
        if node is self.head or node is self.tail:
            raise ValueError("Cannot remove sentinel nodes.")
        
        predecessor = node.prev
        successor = node.next
        
        predecessor.next = successor
        successor.prev = predecessor
        
        # Disconnect node completely for clean garbage collection
        val = node.val
        node.prev = None
        node.next = None
        self._size -= 1
        return val

    def get_at(self, index: int) -> T:
        """
        Retrieves element at index with O(N/2) bidirectional search.
        Chooses head or tail based on proximity to index.
        """
        if not 0 <= index < self._size:
            raise IndexError("Index out of bounds")

        # Bidirectional optimization: walk from closest end
        if index < self._size // 2:
            curr = self.head.next
            for _ in range(index):
                curr = curr.next
        else:
            curr = self.tail.prev
            for _ in range(self._size - 1 - index):
                curr = curr.prev
        return curr.val

    def __iter__(self) -> Iterator[T]:
        curr = self.head.next
        while curr is not self.tail:
            yield curr.val
            curr = curr.next

    def __reversed__(self) -> Iterator[T]:
        curr = self.tail.prev
        while curr is not self.head:
            yield curr.val
            curr = curr.prev

Initial:   [Head] ⇄ [10] ⇄ [20] ⇄ [30] ⇄ [Tail]

Step 1 (Node 10):
  temp = 10.next (20)
  10.next = 10.prev (Head)
  10.prev = temp (20)

Step 2 (Node 20):
  temp = 20.next (30)
  20.next = 20.prev (10)
  20.prev = temp (30)

Step 3 (Node 30):
  temp = 30.next (Tail)
  30.next = 30.prev (20)
  30.prev = temp (Tail)

Final Step:
  Swap wrapper references Head ⇄ Tail.
Result:    [Head] ⇄ [30] ⇄ [20] ⇄ [10] ⇄ [Tail]  (reversed!)

def reverse(self) -> None:
    """In-place pointer reversal in O(N) time and O(1) space."""
    curr = self.head
    while curr is not None:
        # Swap prev and next
        curr.prev, curr.next = curr.next, curr.prev
        # Move forward using the swapped pointer (which was originally .prev)
        curr = curr.prev
    
    # Finally swap head and tail sentinels
    self.head, self.tail = self.tail, self.head

Memory Layout Comparison (64-byte Cache Line):

Array:
[Elem 0 | Elem 1 | Elem 2 | Elem 3 | Elem 4 | Elem 5 | ... ] -> 1 cache line fetch loads 16 elements!

Doubly Linked List:
Heap Addr 0x100: [Node 1] ───(pointer jump)───► Heap Addr 0x940: [Node 2]
(Cache Miss!)                                    (Cache Miss!)

struct Node {
    void* data;
    struct Node* next;
    struct Node* prev;
};

struct list_head {
    struct list_head *next, *prev;
};

// Any struct can be linked into multiple lists simultaneously!
struct task_struct {
    pid_t pid;
    char comm[16];
    struct list_head run_list;     // Links into the scheduler run queue
    struct list_head tasks;        // Links into the global task list
};

from typing import Optional, Any
import collections.abc

class Node[T]:
    """
    A single node in a Doubly Linked List.
    __slots__ prevents dynamic dictionary creation for extreme memory efficiency.
    """
    __slots__ = ("val", "next", "prev")

    def __init__(self, val: T, next_node: Optional['Node[T]'] = None, prev_node: Optional['Node[T]'] = None):
        self.val = val
        self.next = next_node
        self.prev = prev_node

    def __repr__(self) -> str:
        return f"Node({self.val})"


class DoublyLinkedList[T]:
    """
    A highly optimized Doubly Linked List.
    Tracks head, tail, and size.
    """
    __slots__ = ("_head", "_tail", "_size")

    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    @property
    def head(self) -> Optional[Node[T]]:
        return self._head

    @property
    def tail(self) -> Optional[Node[T]]:
        return self._tail

    def __len__(self) -> int:
        """Enables len(my_list) in O(1) time."""
        return self._size

    def __iter__(self) -> collections.abc.Iterator[T]:
        """Enables forward traversal."""
        curr = self._head
        while curr:
            yield curr.val
            curr = curr.next

    def __reversed__(self) -> collections.abc.Iterator[T]:
        """Enables backward traversal: 'for item in reversed(my_list):'"""
        curr = self._tail
        while curr:
            yield curr.val
            curr = curr.prev

    def __repr__(self) -> str:
        """Enables clean printing: 'DLL[1 <-> 2 <-> 3]'"""
        values = " <-> ".join(str(val) for val in self)
        return f"DLL[{values}]"

    def append(self, val: T) -> 'DoublyLinkedList[T]':
        """Adds a node to the END of the list in O(1) time."""
        new_node = Node(val, prev_node=self._tail)
        if self.is_empty:
            self._head = self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1
        return self

    def prepend(self, val: T) -> 'DoublyLinkedList[T]':
        """Adds a node to the FRONT of the list in O(1) time."""
        new_node = Node(val, next_node=self._head)
        if self.is_empty:
            self._head = self._tail = new_node
        else:
            self._head.prev = new_node
            self._head = new_node
        self._size += 1
        return self

    def insert_at(self, index: int, val: T) -> 'DoublyLinkedList[T]':
        """Inserts a node at a specific index in O(N) time."""
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        match index:
            case 0:
                return self.prepend(val)
            case idx if idx == self._size:
                return self.append(val)
            case _:
                # Optimize traversal: choose forward or backward based on index!
                if index < self._size // 2:
                    curr = self._head
                    for _ in range(index):
                        curr = curr.next
                else:
                    curr = self._tail
                    for _ in range(self._size - 1, index, -1):
                        curr = curr.prev
                
                # 'curr' is now the node that currently occupies the insertion index.
                # We want to insert 'new_node' right BEFORE 'curr'.
                prev_node = curr.prev
                new_node = Node(val, next_node=curr, prev_node=prev_node)
                
                if prev_node:
                    prev_node.next = new_node
                curr.prev = new_node
                
                self._size += 1
                return self

    def _remove_node(self, node: Node[T]) -> None:
        """Helper to remove a node directly in O(1) time if reference is known."""
        if node.prev:
            node.prev.next = node.next
        else:
            self._head = node.next  # It was the head
            
        if node.next:
            node.next.prev = node.prev
        else:
            self._tail = node.prev  # It was the tail
            
        self._size -= 1

    def delete(self, val: T) -> bool:
        """Deletes the FIRST occurrence of a value. O(N) time."""
        curr = self._head
        while curr:
            if curr.val == val:
                self._remove_node(curr)
                return True
            curr = curr.next
        return False

    def search(self, val: T) -> bool:
        """Searches for a value in the list. O(N) time."""
        return any(curr_val == val for curr_val in self)

    def reverse(self) -> 'DoublyLinkedList[T]':
        """Reverses the linked list in-place in O(N) time."""
        curr = self._head
        self._tail = self._head  # The old head becomes the new tail

        prev_node = None
        while curr:
            # Swap next and prev pointers
            next_node = curr.next
            curr.next = curr.prev
            curr.prev = next_node
            
            prev_node = curr
            curr = next_node  # Move to what was originally the next node

        self._head = prev_node  # The old tail becomes the new head
        return self


if __name__ == "__main__":
    print("Testing highly optimized Python 3.14 DoublyLinkedList...")
    
    # 1. Initialization and Appending
    dll: DoublyLinkedList[int] = DoublyLinkedList()
    dll.append(1).append(2).append(3)
    
    assert len(dll) == 3
    assert dll.head.val == 1
    assert dll.tail.val == 3
    assert str(dll) == "DLL[1 <-> 2 <-> 3]"
    print("✅ Append & Initialization passed!")

    # 2. Prepending
    dll.prepend(0)
    assert len(dll) == 4
    assert dll.head.val == 0
    assert str(dll) == "DLL[0 <-> 1 <-> 2 <-> 3]"
    print("✅ Prepend passed!")

    # 3. Insertion (Testing half-way optimized traversal)
    # Size is 4. Inserting at index 3 means it'll traverse from the tail!
    dll.insert_at(3, 99)
    assert str(dll) == "DLL[0 <-> 1 <-> 2 <-> 99 <-> 3]"
    assert len(dll) == 5
    print("✅ Insert passed!")

    # 4. Backward Traversal (Testing __reversed__)
    backward = list(reversed(dll))
    assert backward == [3, 99, 2, 1, 0]
    print("✅ Reversed traversal passed!")

    # 5. Deletion
    # Delete from middle
    dll.delete(99)
    assert str(dll) == "DLL[0 <-> 1 <-> 2 <-> 3]"
    # Delete head
    dll.delete(0)
    assert str(dll) == "DLL[1 <-> 2 <-> 3]"
    assert dll.head.val == 1
    # Delete tail
    dll.delete(3)
    assert str(dll) == "DLL[1 <-> 2]"
    assert dll.tail.val == 2
    assert len(dll) == 2
    print("✅ Delete passed!")

    # 6. Reversal
    dll.append(3).append(4)
    assert str(dll) == "DLL[1 <-> 2 <-> 3 <-> 4]"
    dll.reverse()
    assert str(dll) == "DLL[4 <-> 3 <-> 2 <-> 1]"
    assert dll.head.val == 4
    assert dll.tail.val == 1
    print("✅ Reverse in-place passed!")
    
    print("🎉 All DoublyLinkedList tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Merry-Go-Round & Ring Dance
Level 200: Street Fundamentals ────► Cheat card, O(1) rotation superpower, Josephus & Round-Robin
Level 300: Working Professional ───► The Tail-Only pointer trick, infinite loop prevention, clean code
Level 400: Staff & Senior Arch ────► Lock-free ring buffers (LMAX Disruptor), OS CPU scheduling
Level 500: Researcher's Corner ────► The Josephus Recurrence J(n, k) proof & dynamic programming

┌──────────────────────────────────┐
                  │                                  ▼
             ┌─────────┐      ┌─────────┐      ┌─────────┐
             │ Node 1  ├─────►│ Node 2  ├─────►│ Node 3  │
             └─────────┘      └─────────┘      └────┬────┘
                  ▲                                 │
                  └─────────────────────────────────┘

+------------------------------------+
            |                                    |
            v                                    |
Head ---> [ 10 ] ---> [ 20 ] ---> [ 30 ] <--- Tail

curr = self.head
  while True:
      # process curr
      curr = curr.next
      if curr is self.head:
          break

Tail-Only Reference:
self.tail ──────► [ Node 3 (Tail) ]
                       │
                       ▼ (tail.next)
                  [ Node 1 (Head) ] ───► [ Node 2 ] ───► [ Node 3 ]

"""
Enterprise Circular Linked List Implementation
Python 3.14 Compatible
"""
from typing import Optional, Generic, TypeVar, Iterator

T = TypeVar("T")

class Node(Generic[T]):
    __slots__ = ("val", "next")

    def __init__(self, val: T, next_node: Optional["Node[T]"] = None) -> None:
        self.val: T = val
        self.next: Optional["Node[T]"] = next_node

    def __repr__(self) -> str:
        return f"Node({self.val})"


class CircularLinkedList(Generic[T]):
    """
    Circular Linked List maintaining explicit head and tail pointers
    with O(1) rotation and safe cyclic iteration.
    """
    __slots__ = ("_head", "_tail", "_size")

    def __init__(self) -> None:
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._size == 0

    def append(self, val: T) -> None:
        """Appends value to the tail and maintains circular link in O(1)."""
        new_node = Node(val)
        if self._head is None:
            self._head = new_node
            self._tail = new_node
            new_node.next = new_node  # Points to itself
        else:
            assert self._tail is not None
            new_node.next = self._head
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1

    def prepend(self, val: T) -> None:
        """Prepends value to the head in O(1)."""
        new_node = Node(val)
        if self._head is None:
            self._head = new_node
            self._tail = new_node
            new_node.next = new_node
        else:
            assert self._tail is not None
            new_node.next = self._head
            self._head = new_node
            self._tail.next = self._head  # Update tail's loop-back
        self._size += 1

    def rotate(self) -> None:
        """
        Rotates the list forward by 1 step in O(1) time.
        The current head becomes the tail; head.next becomes the new head.
        """
        if self._size <= 1:
            return
        assert self._head is not None and self._tail is not None
        self._tail = self._head
        self._head = self._head.next

    def delete(self, val: T) -> bool:
        """Removes the first occurrence of val. Returns True if found."""
        if self._head is None:
            return False

        curr = self._head
        prev = self._tail

        while True:
            if curr.val == val:
                # Case 1: Only 1 node in list
                if self._size == 1:
                    self._head = None
                    self._tail = None
                else:
                    assert prev is not None and self._tail is not None
                    prev.next = curr.next
                    if curr is self._head:
                        self._head = curr.next
                    if curr is self._tail:
                        self._tail = prev
                self._size -= 1
                return True

            prev = curr
            curr = curr.next
            if curr is self._head:
                break

        return False

    def __iter__(self) -> Iterator[T]:
        """Safe single-pass iteration across all elements without looping infinitely."""
        if self._head is None:
            return
        curr = self._head
        while True:
            yield curr.val
            curr = curr.next
            if curr is self._head:
                break

Initial State:
Head ──► [ 10 ] ──► [ 20 ] ──► [ 30 ] ◄── Tail
  ▲                              │
  └──────────────────────────────┘

Execute: rotate()
Step 1: self._tail = self._head       (Tail moves from 30 to 10)
Step 2: self._head = self._head.next  (Head moves from 10 to 20)

Resulting State:
Head ──► [ 20 ] ──► [ 30 ] ──► [ 10 ] ◄── Tail
  ▲                              │
  └──────────────────────────────┘

[ Process 1 ] ──► [ Process 2 ] ──► [ Process 3 ]
                 ▲                                   │
                 └───────────────────────────────────┘

LMAX Disruptor Ring Buffer (Contiguous Power-of-2 Array):
Index:     [ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]
Sequence:  head_sequence = 1042
Slot:      slot = 1042 & (8 - 1) = 2

def josephus(n: int, k: int) -> int:
    survivor = 0
    for i in range(2, n + 1):
        survivor = (survivor + k) % i
    return survivor

from typing import Optional, Any
import collections.abc

class Node[T]:
    """
    A single node in a Circular Linked List.
    __slots__ prevents dynamic dictionary creation for extreme memory efficiency.
    """
    __slots__ = ("val", "next")

    def __init__(self, val: T, next_node: Optional['Node[T]'] = None):
        self.val = val
        self.next = next_node

    def __repr__(self) -> str:
        return f"Node({self.val})"


class CircularLinkedList[T]:
    """
    A highly optimized Circular Linked List.
    Tracks head, tail, and size. Tail always points back to Head.
    """
    __slots__ = ("_head", "_tail", "_size")

    def __init__(self):
        self._head: Optional[Node[T]] = None
        self._tail: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    @property
    def head(self) -> Optional[Node[T]]:
        return self._head

    @property
    def tail(self) -> Optional[Node[T]]:
        return self._tail

    def __len__(self) -> int:
        """Enables len(my_list) in O(1) time."""
        return self._size

    def __iter__(self) -> collections.abc.Iterator[T]:
        """
        Enables forward traversal. 
        Because it's circular, we MUST stop when we reach the head again to prevent infinite loops!
        """
        if self.is_empty:
            return
            
        curr = self._head
        while True:
            yield curr.val
            curr = curr.next
            if curr == self._head:
                break

    def __repr__(self) -> str:
        """Enables clean printing: 'CLL[1 -> 2 -> 3 -> (back to 1)]'"""
        if self.is_empty:
            return "CLL[]"
        values = " -> ".join(str(val) for val in self)
        return f"CLL[{values} -> (back to {self._head.val})]"

    def append(self, val: T) -> 'CircularLinkedList[T]':
        """Adds a node to the END of the list in O(1) time."""
        new_node = Node(val)
        if self.is_empty:
            self._head = self._tail = new_node
            new_node.next = new_node  # Point to itself to form a circle of 1
        else:
            new_node.next = self._head  # New tail must point back to head
            self._tail.next = new_node  # Old tail points to new tail
            self._tail = new_node
        self._size += 1
        return self

    def prepend(self, val: T) -> 'CircularLinkedList[T]':
        """Adds a node to the FRONT of the list in O(1) time."""
        new_node = Node(val)
        if self.is_empty:
            self._head = self._tail = new_node
            new_node.next = new_node
        else:
            new_node.next = self._head
            self._head = new_node
            self._tail.next = self._head  # Tail must point to the NEW head
        self._size += 1
        return self

    def insert_at(self, index: int, val: T) -> 'CircularLinkedList[T]':
        """Inserts a node at a specific index in O(N) time."""
        if index < 0 or index > self._size:
            raise IndexError("Index out of bounds")

        match index:
            case 0:
                return self.prepend(val)
            case idx if idx == self._size:
                return self.append(val)
            case _:
                curr = self._head
                for _ in range(index - 1):
                    curr = curr.next
                
                new_node = Node(val, curr.next)
                curr.next = new_node
                self._size += 1
                return self

    def rotate(self) -> 'CircularLinkedList[T]':
        """
        Rotates the circular linked list by 1 step in O(1) time.
        The current head becomes the tail, and head.next becomes the new head.
        """
        if self._size > 1:
            self._tail = self._head
            self._head = self._head.next
        return self

    def delete(self, val: T) -> bool:
        """Deletes the FIRST occurrence of a value. O(N) time."""
        if self.is_empty:
            return False

        # Case 1: Deleting the Head
        if self._head.val == val:
            if self._size == 1:
                # Last element being deleted
                self._head = self._tail = None
            else:
                self._head = self._head.next
                self._tail.next = self._head  # Maintain circle
            self._size -= 1
            return True

        # Case 2: Deleting somewhere in the middle or tail
        curr = self._head
        while curr.next != self._head:
            if curr.next.val == val:
                # If we are deleting the tail, we must update the tail pointer
                if curr.next == self._tail:
                    self._tail = curr
                
                curr.next = curr.next.next
                self._size -= 1
                return True
            curr = curr.next

        return False

    def search(self, val: T) -> bool:
        """Searches for a value in the list. O(N) time."""
        return any(curr_val == val for curr_val in self)


if __name__ == "__main__":
    print("Testing highly optimized Python 3.14 CircularLinkedList...")
    
    # 1. Initialization and Appending
    cll: CircularLinkedList[int] = CircularLinkedList()
    cll.append(1).append(2).append(3)
    
    assert len(cll) == 3
    assert cll.head.val == 1
    assert cll.tail.val == 3
    # Check the circular link!
    assert cll.tail.next == cll.head 
    assert str(cll) == "CLL[1 -> 2 -> 3 -> (back to 1)]"
    print("✅ Append & Circular Link passed!")

    # 2. Prepending
    cll.prepend(0)
    assert len(cll) == 4
    assert cll.head.val == 0
    assert cll.tail.next == cll.head
    assert str(cll) == "CLL[0 -> 1 -> 2 -> 3 -> (back to 0)]"
    print("✅ Prepend passed!")

    # 3. Rotate
    cll.rotate()
    assert cll.head.val == 1
    assert cll.tail.val == 0
    assert str(cll) == "CLL[1 -> 2 -> 3 -> 0 -> (back to 1)]"
    print("✅ Rotate O(1) passed!")

    # 4. Deletion
    # Delete middle
    cll.delete(3)
    assert str(cll) == "CLL[1 -> 2 -> 0 -> (back to 1)]"
    
    # Delete head
    cll.delete(1)
    assert cll.head.val == 2
    assert cll.tail.next == cll.head
    assert str(cll) == "CLL[2 -> 0 -> (back to 2)]"
    
    # Delete tail
    cll.delete(0)
    assert cll.tail.val == 2
    assert cll.head.val == 2
    assert cll.tail.next == cll.head
    assert len(cll) == 1
    assert str(cll) == "CLL[2 -> (back to 2)]"
    print("✅ Delete passed!")

    print("🎉 All CircularLinkedList tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Guessing Game & Sorting Funnel
Level 200: Street Fundamentals ────► Cheat card, Inorder invariant, 3 Deletion cases, BST vs Hash
Level 300: Working Professional ───► Clean recursive & iterative code, generator traversals
Level 400: Staff & Senior Arch ────► Degeneration, AVL vs Red-Black, B+ Trees in Database Storage
Level 500: Researcher's Corner ────► Inorder Monotonicity proof, Treaps & Randomized Search Trees

[ 50 ]
                      /      \
            (all < 50)        (all > 50)
             [ 30 ]              [ 70 ]
            /      \            /      \
         [ 20 ]   [ 40 ]     [ 60 ]   [ 80 ]

[ Root: X ]
               /           \
     Left Subtree         Right Subtree
   (ALL keys < X)        (ALL keys > X)

Case 1: Deleting a Leaf Node (No children)
        [ 50 ]                      [ 50 ]
       /      \                    /      \
    [ 30 ]   [ 70 ]      ===>   [ 30 ]    None
               \
             Delete 70 directly -> replace parent's pointer with None.

Case 2: Deleting a Node with 1 Child
        [ 50 ]                      [ 50 ]
       /      \                    /      \
    [ 30 ]   [ 70 ]      ===>   [ 30 ]   [ 80 ]
               \
              [ 80 ]
             Bypass 70: point 50.right directly to 80.

Case 3: Deleting a Node with 2 Children
        [ 50 (Delete!) ]            [ 60 (Successor copied!) ]
       /                \          /                          \
    [ 30 ]             [ 70 ] ===> [ 30 ]                    [ 70 ]
                      /                                       /
                    [ 60 ]                                  None
    Step 1: Find In-Order Successor (smallest node in right subtree = 60).
    Step 2: Copy successor's value (60) into target node (50).
    Step 3: Recursively delete successor (60) from right subtree (Case 1 or 2).

"""
Enterprise Binary Search Tree (BST)
Python 3.14 Compatible
"""
from typing import Optional, Generic, TypeVar, Iterator, Generator

T = TypeVar("T")

class BSTNode(Generic[T]):
    __slots__ = ("val", "left", "right")

    def __init__(self, val: T) -> None:
        self.val: T = val
        self.left: Optional["BSTNode[T]"] = None
        self.right: Optional["BSTNode[T]"] = None

    def __repr__(self) -> str:
        return f"BSTNode({self.val})"


class BinarySearchTree(Generic[T]):
    __slots__ = ("root", "_size")

    def __init__(self) -> None:
        self.root: Optional[BSTNode[T]] = None
        self._size: int = 0

    def __len__(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self.root is None

    def insert(self, val: T) -> None:
        """Inserts value into BST maintaining ordering in O(H)."""
        if self.root is None:
            self.root = BSTNode(val)
            self._size += 1
            return

        curr = self.root
        while True:
            if val < curr.val:
                if curr.left is None:
                    curr.left = BSTNode(val)
                    self._size += 1
                    return
                curr = curr.left
            elif val > curr.val:
                if curr.right is None:
                    curr.right = BSTNode(val)
                    self._size += 1
                    return
                curr = curr.right
            else:
                return  # Value already exists (no duplicates)

    def search(self, val: T) -> bool:
        """Iterative search in O(H) time and O(1) space."""
        curr = self.root
        while curr is not None:
            if val == curr.val:
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return False

    def delete(self, val: T) -> bool:
        """Deletes a node by value. Returns True if deleted."""
        initial_size = self._size
        self.root = self._delete_recursive(self.root, val)
        return self._size < initial_size

    def _delete_recursive(
        self, node: Optional[BSTNode[T]], val: T
    ) -> Optional[BSTNode[T]]:
        if node is None:
            return None

        if val < node.val:
            node.left = self._delete_recursive(node.left, val)
        elif val > node.val:
            node.right = self._delete_recursive(node.right, val)
        else:
            # Found node to delete!
            self._size -= 1
            # Case 1 & 2: 0 or 1 child
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left

            # Case 3: 2 children. Find in-order successor (min in right subtree)
            successor = self._find_min(node.right)
            node.val = successor.val
            # Delete successor from right subtree (size already decremented above, restore temporarily)
            self._size += 1
            node.right = self._delete_recursive(node.right, successor.val)

        return node

    def _find_min(self, node: BSTNode[T]) -> BSTNode[T]:
        curr = node
        while curr.left is not None:
            curr = curr.left
        return curr

    def inorder(self) -> Generator[T, None, None]:
        """Generator yielding elements in strictly sorted order: Left -> Root -> Right."""
        yield from self._inorder_helper(self.root)

    def _inorder_helper(self, node: Optional[BSTNode[T]]) -> Generator[T, None, None]:
        if node is not None:
            yield from self._inorder_helper(node.left)
            yield node.val
            yield from self._inorder_helper(node.right)

Balanced Tree (Optimal):              Skewed Tree (Degenerate):
          30                                   10
        /    \                                   \
      20      40                                  20
     /          \                                   \
   10            50                                  30
                                                       \
                                                        40
                                                          \
                                                           50
Height = log2(N)                               Height = N

from typing import Optional, Generator
import collections.abc

class Node[T]:
    __slots__ = ("val", "left", "right")

    def __init__(self, val: T):
        self.val = val
        self.left: Optional['Node[T]'] = None
        self.right: Optional['Node[T]'] = None

    def __repr__(self) -> str:
        return f"Node({self.val})"


class BinarySearchTree[T]:
    __slots__ = ("root", "_size")

    def __init__(self):
        self.root: Optional[Node[T]] = None
        self._size: int = 0

    @property
    def is_empty(self) -> bool:
        return self._size == 0

    def __len__(self) -> int:
        return self._size

    def insert(self, val: T) -> None:
        """Inserts a value into the BST. O(H) time."""
        if not self.root:
            self.root = Node(val)
            self._size += 1
            return
            
        curr = self.root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = Node(val)
                    self._size += 1
                    return
                curr = curr.left
            elif val > curr.val:
                if not curr.right:
                    curr.right = Node(val)
                    self._size += 1
                    return
                curr = curr.right
            else:
                # Value already exists, ignore (or handle duplicates if desired)
                return

    def search(self, val: T) -> bool:
        """Searches for a value in the BST. O(H) time."""
        curr = self.root
        while curr:
            if val == curr.val:
                return True
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return False

    def delete(self, val: T) -> bool:
        """Deletes a value from the BST. Returns True if deleted. O(H) time."""
        def _delete_recursive(node: Optional[Node[T]], target: T) -> tuple[Optional[Node[T]], bool]:
            if not node:
                return None, False
                
            if target < node.val:
                node.left, deleted = _delete_recursive(node.left, target)
                return node, deleted
            elif target > node.val:
                node.right, deleted = _delete_recursive(node.right, target)
                return node, deleted
            else:
                # We found the node to delete!
                
                # Case 1 & 2: 0 or 1 child
                if not node.left:
                    return node.right, True
                elif not node.right:
                    return node.left, True
                    
                # Case 3: 2 children. Find in-order successor (min of right subtree)
                successor = node.right
                while successor.left:
                    successor = successor.left
                    
                # Copy successor value to this node
                node.val = successor.val
                # Delete the successor from the right subtree
                node.right, _ = _delete_recursive(node.right, successor.val)
                return node, True

        self.root, deleted = _delete_recursive(self.root, val)
        if deleted:
            self._size -= 1
        return deleted

    # --- Traversals Using Generators ---
    
    def in_order(self) -> Generator[T, None, None]:
        """Left -> Root -> Right. Yields elements in sorted order."""
        def _traverse(node: Optional[Node[T]]):
            if node:
                yield from _traverse(node.left)
                yield node.val
                yield from _traverse(node.right)
        yield from _traverse(self.root)

    def pre_order(self) -> Generator[T, None, None]:
        """Root -> Left -> Right. Good for making a copy of the tree."""
        def _traverse(node: Optional[Node[T]]):
            if node:
                yield node.val
                yield from _traverse(node.left)
                yield from _traverse(node.right)
        yield from _traverse(self.root)

    def post_order(self) -> Generator[T, None, None]:
        """Left -> Right -> Root. Good for deleting the tree."""
        def _traverse(node: Optional[Node[T]]):
            if node:
                yield from _traverse(node.left)
                yield from _traverse(node.right)
                yield node.val
        yield from _traverse(self.root)


if __name__ == "__main__":
    print("Testing Binary Search Tree...")
    bst: BinarySearchTree[int] = BinarySearchTree()
    
    # 1. Insert
    for num in [50, 30, 20, 40, 70, 60, 80]:
        bst.insert(num)
        
    assert len(bst) == 7
    print("✅ Insert passed!")

    # 2. Traversals
    in_order_list = list(bst.in_order())
    assert in_order_list == [20, 30, 40, 50, 60, 70, 80]
    
    pre_order_list = list(bst.pre_order())
    assert pre_order_list == [50, 30, 20, 40, 70, 60, 80]
    
    post_order_list = list(bst.post_order())
    assert post_order_list == [20, 40, 30, 60, 80, 70, 50]
    print("✅ Traversals passed!")

    # 3. Search
    assert bst.search(60) is True
    assert bst.search(99) is False
    print("✅ Search passed!")

    # 4. Delete
    # Leaf node (20)
    bst.delete(20)
    assert list(bst.in_order()) == [30, 40, 50, 60, 70, 80]
    
    # Node with 1 child (30 now only has 40)
    bst.delete(30)
    assert list(bst.in_order()) == [40, 50, 60, 70, 80]
    
    # Node with 2 children (70 has 60 and 80)
    bst.delete(70)
    assert list(bst.in_order()) == [40, 50, 60, 80]
    
    # Delete Root (50)
    bst.delete(50)
    assert list(bst.in_order()) == [40, 60, 80]
    assert bst.root.val == 60  # 60 is the in-order successor of 50
    assert len(bst) == 3
    print("✅ Delete passed!")

    print("🎉 All BST tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Hospital Triage Desk & Array Tree
Level 200: Street Fundamentals ────► Cheat card, Top-K Inversion Rule, Floyd's O(N) heapify
Level 300: Working Professional ───► Generic Min/Max heap in Python 3.14 with custom key extractors
Level 400: Staff & Senior Arch ────► Cache line alignment, D-ary Heaps, Dijkstra in OSPF routing
Level 500: Researcher's Corner ────► Summation proof of linear heapify, Fibonacci Heap amortized O(1)

Conceptual Complete Binary Tree:             Flat Array Representation:
               [ 0: (4) ]                     Index:  0   1   2   3   4
              /          \                    Value: [4 | 10| 15| 20| 25]
        [ 1: (10) ]    [ 2: (15) ]
       /          \
  [ 3: (20) ]   [ 4: (25) ]

Min-Heap Property: Parent <= Children  ===>  Root is ALWAYS the Global Minimum
Max-Heap Property: Parent >= Children  ===>  Root is ALWAYS the Global Maximum

┌─────────────────────────────────────────────────────────────────────────────┐
│  To find Top-K LARGEST elements  ════► Maintain a MIN-HEAP of size K!       │
│  To find Top-K SMALLEST elements ════► Maintain a MAX-HEAP of size K!       │
└─────────────────────────────────────────────────────────────────────────────┘

┌────────────────────────┐
                           │ Need Extremum Element? │
                           │ (Min or Max repeatedly)│
                           └───────────┬────────────┘
                                       │
                          YES ─────────┴───────── NO
                           │                       │
                 ┌───────────────────┐    ┌─────────────────┐
                 │ Need Total Order  │    │ Hash Table or   │
                 │ or Range Queries? │    │ Balanced Tree   │
                 └─────────┬─────────┘    └─────────────────┘
                           │
              YES ─────────┴───────── NO
               │                       │
      ┌─────────────────┐    ┌────────────────────┐
      │ Balanced BST    │    │ Binary Heap / PQ   │
      │ (e.g. TreeMap)  │    │ O(1) peek, O(logN) │
      │ O(log N) all    │    │ O(N) array storage │
      └─────────────────┘    └────────────────────┘

"""
Enterprise Generic Min/Max Heap Implementation
Python 3.14 Compatible
"""
from typing import List, Optional, Callable, Any, Generic, TypeVar

T = TypeVar("T")

class Heap(Generic[T]):
    """
    Highly optimized Array-backed Binary Heap supporting both Min and Max configurations
    with optional custom key extractors.
    """
    __slots__ = ("_data", "_is_min", "_key")

    def __init__(
        self,
        is_min_heap: bool = True,
        key: Optional[Callable[[T], Any]] = None,
        initial_data: Optional[List[T]] = None,
    ) -> None:
        self._is_min = is_min_heap
        self._key = key if key is not None else lambda x: x
        self._data: List[T] = []

        if initial_data:
            self._data = list(initial_data)
            self._build_heap()

    def __len__(self) -> int:
        return len(self._data)

    def is_empty(self) -> bool:
        return len(self._data) == 0

    def peek(self) -> T:
        """Returns the extreme element in O(1) time without removing it."""
        if not self._data:
            raise IndexError("peek from empty heap")
        return self._data[0]

    def push(self, val: T) -> None:
        """Pushes a new value into the heap in O(log N) time."""
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self) -> T:
        """Extracts and returns the extreme element in O(log N) time."""
        if not self._data:
            raise IndexError("pop from empty heap")

        root = self._data[0]
        last_val = self._data.pop()

        if self._data:
            self._data[0] = last_val
            self._sift_down(0)

        return root

    def _compare(self, idx1: int, idx2: int) -> bool:
        """Returns True if idx1 has higher priority than idx2."""
        val1 = self._key(self._data[idx1])
        val2 = self._key(self._data[idx2])
        return val1 < val2 if self._is_min else val1 > val2

    def _sift_up(self, idx: int) -> None:
        """Bubbles an element up to restore the heap property in O(log N)."""
        curr = idx
        while curr > 0:
            parent = (curr - 1) // 2
            if self._compare(curr, parent):
                self._data[curr], self._data[parent] = self._data[parent], self._data[curr]
                curr = parent
            else:
                break

    def _sift_down(self, idx: int) -> None:
        """Bubbles an element down to restore the heap property in O(log N)."""
        curr = idx
        n = len(self._data)

        while True:
            left = 2 * curr + 1
            right = 2 * curr + 2
            priority_idx = curr

            if left < n and self._compare(left, priority_idx):
                priority_idx = left
            if right < n and self._compare(right, priority_idx):
                priority_idx = right

            if priority_idx != curr:
                self._data[curr], self._data[priority_idx] = (
                    self._data[priority_idx],
                    self._data[curr],
                )
                curr = priority_idx
            else:
                break

    def _build_heap(self) -> None:
        """Floyd's Algorithm: Builds a heap in linear O(N) time bottom-up."""
        # Start from last non-leaf node down to root
        for i in reversed(range(len(self._data) // 2)):
            self._sift_down(i)

1. Append to end:
   Array: [10, 15, 4]
   Tree:      10 (idx 0)
             /   \
      15 (idx 1)  4 (idx 2)

2. _sift_up(2):
   Parent of idx 2 is (2 - 1) // 2 = 0 (Val 10).
   Compare: 4 < 10 -> Priority violation! Swap!
   Array: [4, 15, 10]
   Tree:       4 (idx 0)
             /   \
      15 (idx 1)  10 (idx 2)
   idx 0 is root -> Complete!

from typing import Generic, TypeVar, Optional, List, Callable, Any

T = TypeVar('T')

class Heap(Generic[T]):
    __slots__ = ("_data", "_is_min_heap", "_compare")

    def __init__(self, is_min_heap: bool = True, key: Optional[Callable[[T], Any]] = None):
        self._data: List[T] = []
        self._is_min_heap = is_min_heap
        
        # Determine the comparison function based on min/max and custom key
        if key:
            if self._is_min_heap:
                self._compare = lambda a, b: key(a) < key(b)
            else:
                self._compare = lambda a, b: key(a) > key(b)
        else:
            if self._is_min_heap:
                self._compare = lambda a, b: a < b
            else:
                self._compare = lambda a, b: a > b

    @property
    def is_empty(self) -> bool:
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)
        
    def __repr__(self) -> str:
        kind = "MinHeap" if self._is_min_heap else "MaxHeap"
        return f"{kind}({self._data})"

    def _swap(self, i: int, j: int) -> None:
        self._data[i], self._data[j] = self._data[j], self._data[i]

    def _sift_up(self, index: int) -> None:
        """Bubble the element up until heap property is restored."""
        while index > 0:
            parent_idx = (index - 1) // 2
            # If the current element should be "above" its parent based on comparison
            if self._compare(self._data[index], self._data[parent_idx]):
                self._swap(index, parent_idx)
                index = parent_idx
            else:
                break

    def _sift_down(self, index: int) -> None:
        """Bubble the element down until heap property is restored."""
        size = len(self._data)
        
        while True:
            left_idx = 2 * index + 1
            right_idx = 2 * index + 2
            extreme_idx = index  # smallest for MinHeap, largest for MaxHeap

            # Check if left child is more "extreme" than current extreme
            if left_idx < size and self._compare(self._data[left_idx], self._data[extreme_idx]):
                extreme_idx = left_idx
                
            # Check if right child is more "extreme" than current extreme
            if right_idx < size and self._compare(self._data[right_idx], self._data[extreme_idx]):
                extreme_idx = right_idx

            if extreme_idx != index:
                self._swap(index, extreme_idx)
                index = extreme_idx
            else:
                break

    def push(self, val: T) -> None:
        """Adds a value to the heap in O(log N) time."""
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self) -> T:
        """Removes and returns the extreme (min/max) value in O(log N) time."""
        if self.is_empty:
            raise IndexError("pop from empty heap")
            
        # If there's only 1 element, just pop it directly
        if len(self._data) == 1:
            return self._data.pop()
            
        extreme_val = self._data[0]
        # Move the last leaf to the root, then sift it down
        self._data[0] = self._data.pop()
        self._sift_down(0)
        
        return extreme_val

    def peek(self) -> T:
        """Returns the extreme value without removing it in O(1) time."""
        if self.is_empty:
            raise IndexError("peek from empty heap")
        return self._data[0]


if __name__ == "__main__":
    print("Testing MinHeap...")
    min_heap: Heap[int] = Heap(is_min_heap=True)
    for num in [10, 4, 15, 20, 0, 30]:
        min_heap.push(num)
        
    assert min_heap.peek() == 0
    assert min_heap.pop() == 0
    assert min_heap.pop() == 4
    assert min_heap.pop() == 10
    assert len(min_heap) == 3
    print("✅ MinHeap passed!")

    print("\nTesting MaxHeap...")
    max_heap: Heap[int] = Heap(is_min_heap=False)
    for num in [10, 4, 15, 20, 0, 30]:
        max_heap.push(num)
        
    assert max_heap.peek() == 30
    assert max_heap.pop() == 30
    assert max_heap.pop() == 20
    assert max_heap.pop() == 15
    assert len(max_heap) == 3
    print("✅ MaxHeap passed!")
    
    print("\nTesting Custom Key Heap (Sort by string length)...")
    len_heap: Heap[str] = Heap(is_min_heap=True, key=lambda x: len(x))
    len_heap.push("Apple")
    len_heap.push("Kiwi")
    len_heap.push("Strawberry")
    
    assert len_heap.pop() == "Kiwi"
    assert len_heap.pop() == "Apple"
    print("✅ Custom Key Heap passed!")

    print("\n🎉 All Heap tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Autocomplete Funnel & Letter Tree
Level 200: Street Fundamentals ────► Cheat card, 4 FAANG patterns, Word Search II triage rules
Level 300: Working Professional ───► Clean typed Trie with wildcard search and prefix retrieval
Level 400: Staff & Senior Arch ────► Radix Trees (Patricia), Aho-Corasick multi-pattern matching
Level 500: Researcher's Corner ────► Suffix Trees, Ukkonen's O(N) linear time, BWT in Genomics

(Root)
                         │ 'a'
                        [ a ]
                         │ 'p'
                        [ p ]
                         │ 'p'
                     [ p (End: "app") ]
                     /       \
               'l'  /         \  'e'
                  [ l ]       [ e ]
                   │ 'e'       │ 't'
           [ e (End: "apple") ] [ t (End: "appetizer"...) ]

TrieNode:
  - children: dict[str, TrieNode]  (or fixed array [None] * 26)
  - is_end_of_word: bool           (Distinguishes prefix from complete word)
  - pass_count: int                (Tracks how many words share this prefix)

"""
Enterprise Trie (Prefix Tree) Implementation
Python 3.14 Compatible
"""
from typing import Dict, List, Optional

class TrieNode:
    __slots__ = ("children", "is_end_of_word")

    def __init__(self) -> None:
        self.children: Dict[str, TrieNode] = {}
        self.is_end_of_word: bool = False

    def __repr__(self) -> str:
        return f"TrieNode(is_end={self.is_end_of_word}, children={list(self.children.keys())})"


class Trie:
    """
    Prefix Tree supporting insertion, exact search, prefix matching,
    wildcard queries, and autocomplete suggestion retrieval.
    """
    __slots__ = ("root",)

    def __init__(self) -> None:
        self.root: TrieNode = TrieNode()

    def insert(self, word: str) -> None:
        """Inserts a word into the Trie in O(L) time."""
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Returns True if the exact word exists in O(L) time."""
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Returns True if there is any word that begins with prefix in O(L) time."""
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True

    def autocomplete(self, prefix: str, limit: int = 5) -> List[str]:
        """Returns up to `limit` words starting with the given prefix."""
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return []
            curr = curr.children[char]

        results: List[str] = []

        def _dfs(node: TrieNode, path: List[str]) -> None:
            if len(results) >= limit:
                return
            if node.is_end_of_word:
                results.append(prefix + "".join(path))
            for char, child_node in sorted(node.children.items()):
                path.append(char)
                _dfs(child_node, path)
                path.pop()

        _dfs(curr, [])
        return results

Board:
  [ 'o', 'a', 'a', 'n' ]
  [ 'e', 't', 'a', 'e' ]
  [ 'i', 'h', 'k', 'r' ]
  [ 'i', 'f', 'l', 'v' ]

1. Load all words into Trie:
   Root -> 'o' -> 'a' -> 't' -> 'h' (End)
   Root -> 'p' -> 'e' -> 'a' (End)
   ...

2. DFS starts at cell (0, 0) = 'o':
   - 'o' exists in Root.children! Step into TrieNode('o').
   - Move to neighbor (0, 1) = 'a':
     - 'a' exists in TrieNode('o').children! Step into TrieNode('a').
   - Move to neighbor (1, 1) = 't':
     - 't' exists in TrieNode('a').children! Step into TrieNode('t').
   - Move to neighbor (2, 1) = 'h':
     - 'h' exists in TrieNode('t').children! Step into TrieNode('h').
     - TrieNode('h').is_end_of_word == True! ===> FOUND "oath"! ✅

3. DFS starts at cell (2, 2) = 'k':
   - 'k' NOT in Root.children.
   - PRUNE ENTIRE SUBTREE IMMEDIATELY! 0 wasted recursive steps!

class TrieNode:
    """
    A single node in the Trie.
    __slots__ ensures we don't waste memory on dynamic dictionaries, except 
    for the explicit 'children' dict we need!
    """
    __slots__ = ("children", "is_end_of_word")

    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.is_end_of_word: bool = False

    def __repr__(self) -> str:
        return f"TrieNode(children={list(self.children.keys())}, is_end={self.is_end_of_word})"


class Trie:
    """
    A highly optimized Prefix Tree.
    """
    __slots__ = ("root",)

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """Inserts a word into the trie in O(L) time."""
        curr = self.root
        for char in word:
            if char not in curr.children:
                curr.children[char] = TrieNode()
            curr = curr.children[char]
        curr.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Returns True if the exact word is in the trie. O(L) time."""
        curr = self.root
        for char in word:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return curr.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Returns True if there is any word in the trie that starts with the given prefix. O(L) time."""
        curr = self.root
        for char in prefix:
            if char not in curr.children:
                return False
            curr = curr.children[char]
        return True


if __name__ == "__main__":
    print("Testing Trie (Prefix Tree)...")
    trie = Trie()
    
    # 1. Insert
    trie.insert("apple")
    print("✅ Inserted 'apple'")

    # 2. Search
    assert trie.search("apple") is True
    assert trie.search("app") is False
    print("✅ Search passed!")

    # 3. StartsWith
    assert trie.starts_with("app") is True
    assert trie.starts_with("apl") is False
    print("✅ StartsWith passed!")

    # 4. Insert Sub-word
    trie.insert("app")
    assert trie.search("app") is True
    print("✅ Insert Sub-word passed!")
    
    print("🎉 All Trie tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

Level 100: The Napkin Sketch ──────► 30s physical analogy: The Airline Route Map & Friendship Web
Level 200: Street Fundamentals ────► Cheat card, Adjacency List vs Matrix, 5 FAANG graph archetypes
Level 300: Working Professional ───► Generic Graph class with BFS/DFS generators and cycle detection
Level 400: Staff & Senior Arch ────► Scale limits (Billions of edges), CSR memory format, Pregel BSP
Level 500: Researcher's Corner ────► Handshaking Lemma, Graph Laplacian L = D - A & Cheeger's Bound

(New York) ────── 7h ──────► (London)
              │                           │
             14h                         12h
              ▼                           ▼
           (Tokyo) ◄────── 9h ──────── (Dubai)

Graph Invariants:
- Undirected: Edge (u, v) implies (v, u) exists. Degree = number of incident edges.
- Directed (DAG): Edges have arrowheads. In-degree != Out-degree.
- Dense Graph: E ≈ V²   ===> Use Adjacency Matrix
- Sparse Graph: E ≪ V²  ===> Use Adjacency List (99.9% of FAANG problems!)

┌────────────────────────┐
                             │ What is the problem?   │
                             └───────────┬────────────┘
                                         │
         ┌───────────────────┬───────────┴───────────┬───────────────────┐
         ▼                   ▼                       ▼                   ▼
   Shortest Path?       Cycle in DAG /          Connected Components?   Explore All Paths?
         │             Course Prereqs?               │                   │
         │                   │                       │                   │
   Weighted?           Topological Sort        BFS / DFS / Union-Find   Backtracking DFS
   ┌─────┴─────┐      (Kahn's In-Degree)      (Number of Islands)      (All Paths to Dest)
   ▼           ▼
Unweighted:  Weighted:
  BFS        Dijkstra
(O(V+E))   (O(E log V))

visited = set()
  for node in graph:
      if node not in visited:
          bfs(node, visited)

"""
Enterprise Generic Graph Implementation (Adjacency List)
Python 3.14 Compatible
"""
from typing import Dict, Set, List, Optional, Generic, TypeVar, Iterator
from collections import deque

T = TypeVar("T")

class Graph(Generic[T]):
    """
    Adjacency list graph supporting directed and undirected configurations,
    vertex/edge management, and BFS/DFS traversals.
    """
    __slots__ = ("_adj", "_is_directed")

    def __init__(self, is_directed: bool = False) -> None:
        self._adj: Dict[T, Set[T]] = {}
        self._is_directed: bool = is_directed

    def add_vertex(self, vertex: T) -> None:
        """Adds a vertex to the graph if not already present."""
        if vertex not in self._adj:
            self._adj[vertex] = set()

    def add_edge(self, u: T, v: T) -> None:
        """Adds an edge from u to v. In undirected mode, adds v to u as well."""
        self.add_vertex(u)
        self.add_vertex(v)
        self._adj[u].add(v)
        if not self._is_directed:
            self._adj[v].add(u)

    def remove_edge(self, u: T, v: T) -> None:
        """Removes the edge between u and v."""
        if u in self._adj and v in self._adj[u]:
            self._adj[u].remove(v)
        if not self._is_directed and v in self._adj and u in self._adj[v]:
            self._adj[v].remove(u)

    def remove_vertex(self, vertex: T) -> None:
        """Removes a vertex and all incident edges across the graph."""
        if vertex not in self._adj:
            return
        del self._adj[vertex]
        for neighbors in self._adj.values():
            neighbors.discard(vertex)

    def get_neighbors(self, vertex: T) -> Set[T]:
        """Returns the set of neighbors for a vertex."""
        return self._adj.get(vertex, set())

    def bfs(self, start: T) -> Iterator[T]:
        """Breadth-First Search traversal yielding visited vertices in level order."""
        if start not in self._adj:
            return
        visited: Set[T] = {start}
        queue: deque[T] = deque([start])

        while queue:
            curr = queue.popleft()
            yield curr
            for neighbor in sorted(self._adj[curr], key=lambda x: str(x)):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

    def dfs(self, start: T) -> Iterator[T]:
        """Depth-First Search traversal yielding visited vertices."""
        if start not in self._adj:
            return
        visited: Set[T] = set()

        def _dfs_helper(node: T) -> Iterator[T]:
            visited.add(node)
            yield node
            for neighbor in sorted(self._adj[node], key=lambda x: str(x)):
                if neighbor not in visited:
                    yield from _dfs_helper(neighbor)

        yield from _dfs_helper(start)

1. Compute in-degrees:
   in_degree = {0: 2, 1: 1, 2: 1, 3: 0}

2. Initialize queue with vertices having in_degree == 0:
   Queue: [ 3 ]

3. Process Queue:
   - Pop 3: Result = [ 3 ]
     - Decrement neighbors: in_degree[1] -> 0, in_degree[2] -> 0
     - Enqueue 1 and 2: Queue = [ 1, 2 ]
   - Pop 1: Result = [ 3, 1 ]
     - Decrement neighbor: in_degree[0] -> 1
   - Pop 2: Result = [ 3, 1, 2 ]
     - Decrement neighbor: in_degree[0] -> 0
     - Enqueue 0: Queue = [ 0 ]
   - Pop 0: Result = [ 3, 1, 2, 0 ]

4. Verification: len(Result) == V (4 == 4).
   Valid Topological Ordering: [ 3, 1, 2, 0 ] ✅

Graph:
Node 0 -> Neighbors: [ 1, 2 ]
Node 1 -> Neighbors: [ 2 ]
Node 2 -> Neighbors: [ 0, 3 ]
Node 3 -> Neighbors: [ ]

CSR Representation:
col_idx:  [ 1, 2,  2,  0, 3 ]   <--- Contiguous flat array of all target edges
row_ptr:  [ 0,     2,  3,     5, 5 ] <--- Offsets into col_idx for each vertex

from typing import Generic, TypeVar, Optional, Generator
import collections.abc

T = TypeVar('T')

class Graph(Generic[T]):
    __slots__ = ("_adj_list", "_is_directed")

    def __init__(self, is_directed: bool = False):
        # We use a set for neighbors for O(1) edge lookups and removals!
        self._adj_list: dict[T, set[T]] = {}
        self._is_directed = is_directed

    @property
    def vertex_count(self) -> int:
        return len(self._adj_list)

    @property
    def edge_count(self) -> int:
        count = sum(len(neighbors) for neighbors in self._adj_list.values())
        return count if self._is_directed else count // 2

    def __contains__(self, vertex: T) -> bool:
        """Enables 'if vertex in graph:'"""
        return vertex in self._adj_list

    def __repr__(self) -> str:
        kind = "DirectedGraph" if self._is_directed else "UndirectedGraph"
        return f"{kind}(Vertices: {self.vertex_count}, Edges: {self.edge_count})"

    def add_vertex(self, vertex: T) -> None:
        """Adds a vertex to the graph in O(1) time."""
        if vertex not in self._adj_list:
            self._adj_list[vertex] = set()

    def add_edge(self, src: T, dst: T) -> None:
        """Adds an edge between src and dst in O(1) time."""
        # Ensure both vertices exist
        self.add_vertex(src)
        self.add_vertex(dst)
        
        self._adj_list[src].add(dst)
        if not self._is_directed:
            self._adj_list[dst].add(src)

    def remove_edge(self, src: T, dst: T) -> None:
        """Removes the edge between src and dst in O(1) time."""
        if src in self._adj_list and dst in self._adj_list[src]:
            self._adj_list[src].remove(dst)
            
        if not self._is_directed:
            if dst in self._adj_list and src in self._adj_list[dst]:
                self._adj_list[dst].remove(src)

    def remove_vertex(self, vertex: T) -> None:
        """Removes a vertex and ALL its connected edges in O(V) time."""
        if vertex not in self._adj_list:
            return
            
        # 1. Remove the vertex completely from the adjacency list
        del self._adj_list[vertex]
        
        # 2. Iterate through all other vertices and remove this vertex from their sets
        for neighbors in self._adj_list.values():
            neighbors.discard(vertex)  # discard removes without throwing KeyError

    def get_neighbors(self, vertex: T) -> set[T]:
        """Returns the neighbors of a vertex in O(1) time."""
        if vertex not in self._adj_list:
            raise KeyError(f"Vertex {vertex} not found in graph.")
        return self._adj_list[vertex]

    def get_vertices(self) -> list[T]:
        """Returns all vertices in the graph."""
        return list(self._adj_list.keys())


if __name__ == "__main__":
    print("Testing Undirected Graph...")
    graph: Graph[str] = Graph(is_directed=False)
    
    # Add vertices and edges
    graph.add_edge("A", "B")
    graph.add_edge("B", "C")
    graph.add_edge("C", "A")
    
    assert graph.vertex_count == 3
    assert graph.edge_count == 3
    assert "B" in graph.get_neighbors("A")
    assert "A" in graph.get_neighbors("B")
    print("✅ Add Edges passed!")

    # Remove Edge
    graph.remove_edge("A", "B")
    assert "B" not in graph.get_neighbors("A")
    assert "A" not in graph.get_neighbors("B")
    assert graph.edge_count == 2
    print("✅ Remove Edge passed!")

    # Remove Vertex
    graph.remove_vertex("C")
    assert "C" not in graph
    assert graph.vertex_count == 2
    assert graph.edge_count == 0  # C held the last two edges
    print("✅ Remove Vertex passed!")
    
    print("\nTesting Directed Graph...")
    di_graph: Graph[int] = Graph(is_directed=True)
    di_graph.add_edge(1, 2)
    
    assert 2 in di_graph.get_neighbors(1)
    assert 1 not in di_graph.get_neighbors(2)  # One-way street!
    assert di_graph.edge_count == 1
    print("✅ Directed Edges passed!")

    print("\n🎉 All Graph tests passed successfully!")

# ==============================================================================
# ⚠️ PYTHON < 3.12 COMPATIBILITY FALLBACK
# ==============================================================================
# The modern `class Name[T]:` syntax (PEP 695) requires Python 3.12+.
# If you are running this code in an older environment (like an online IDE), 
# you will get a "SyntaxError: invalid syntax".
# 
# To fix this, replace the modern syntax with the traditional Generic typing:
# 
# 1. Import Generic and TypeVar:
#    from typing import Generic, TypeVar
# 
# 2. Define the TypeVar:
#    T = TypeVar('T')
# 
# 3. Inherit from Generic[T]:
#    class Node(Generic[T]):
#        ...
#    
#    class DataStructure(Generic[T]):
#        ...
# ==============================================================================

[ Village A ] (Mayor A)       [ Village B ] (Mayor B)

Before Path Compression (Winding path):
X ──> Village 1 ──> Village 2 ──> Village 3 ──> Supreme Leader

After Path Compression (Flattened):
X ──────────────────────────────────────────> Supreme Leader

class DSU:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, i: int) -> int:
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]

    def union(self, i: int, j: int) -> bool:
        root_i, root_j = self.find(i), self.find(j)
        if root_i == root_j:
            return False  # Already connected (Detected a cycle!)
        # Union by rank: attach smaller tree under taller tree
        if self.rank[root_i] < self.rank[root_j]:
            self.parent[root_i] = root_j
        elif self.rank[root_i] > self.rank[root_j]:
            self.parent[root_j] = root_i
        else:
            self.parent[root_j] = root_i
            self.rank[root_i] += 1
        return True

"""
Production Union-Find (Disjoint-Set Union) Implementation.
Includes path compression, union-by-size, component counting, and maximum cluster size.
"""

from typing import List, Tuple

class UnionFind:
    """Disjoint-Set Union supporting O(alpha(N)) operations."""

    def __init__(self, n: int) -> None:
        self._n = n
        self.parent: List[int] = list(range(n))
        self.size: List[int] = [1] * n  # Union by size
        self.num_components: int = n
        self.max_component_size: int = 1 if n > 0 else 0

    def find(self, x: int) -> int:
        """Finds representative with two-pass full path compression."""
        root = x
        while root != self.parent[root]:
            root = self.parent[root]

        # Path compression: point all ancestors directly to root
        curr = x
        while curr != root:
            nxt = self.parent[curr]
            self.parent[curr] = root
            curr = nxt

        return root

    def union(self, x: int, y: int) -> bool:
        """Merges sets containing x and y. Returns True if merged, False if already connected."""
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        # Union by size: attach smaller tree under larger tree
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        self.num_components -= 1

        if self.size[root_x] > self.max_component_size:
            self.max_component_size = self.size[root_x]

        return True

    def connected(self, x: int, y: int) -> bool:
        """Checks if x and y belong to the same component."""
        return self.find(x) == self.find(y)

    def get_component_size(self, x: int) -> int:
        """Returns the number of elements in x's component."""
        return self.size[self.find(x)]

from typing import List


class UnionFind:
    """Disjoint-Set Union supporting near-constant time operations.

    Complexity:
        - find(x): O(alpha(N)) amortized
        - union(x, y): O(alpha(N)) amortized
        - connected(x, y): O(alpha(N)) amortized
        - Space: O(N)
    """

    def __init__(self, n: int) -> None:
        """Initializes DSU with N disjoint singleton sets [0 ... N-1]."""
        self._n = n
        self.parent: List[int] = list(range(n))
        self.size: List[int] = [1] * n
        self.num_components: int = n
        self.max_component_size: int = 1 if n > 0 else 0

    def find(self, x: int) -> int:
        """Finds representative of x's set with iterative path compression."""
        root = x
        while root != self.parent[root]:
            root = self.parent[root]

        # Path compression: update ancestors to point directly to root
        curr = x
        while curr != root:
            nxt = self.parent[curr]
            self.parent[curr] = root
            curr = nxt

        return root

    def union(self, x: int, y: int) -> bool:
        """Merges sets containing x and y.

        Returns:
            True if elements were in separate sets and merged.
            False if elements were already in the same set (detected a cycle!).
        """
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False

        # Union by size: attach smaller tree under larger tree
        if self.size[root_x] < self.size[root_y]:
            root_x, root_y = root_y, root_x

        self.parent[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        self.num_components -= 1

        if self.size[root_x] > self.max_component_size:
            self.max_component_size = self.size[root_x]

        return True

    def connected(self, x: int, y: int) -> bool:
        """Returns True if x and y share the same component root."""
        return self.find(x) == self.find(y)

    def get_component_size(self, x: int) -> int:
        """Returns the number of elements in the component containing x."""
        return self.size[self.find(x)]


def test_union_find() -> None:
    """Unit tests verifying UnionFind correctness and component tracking."""
    uf = UnionFind(6)
    assert uf.num_components == 6
    assert uf.max_component_size == 1

    # Merge {0, 1}
    assert uf.union(0, 1) is True
    assert uf.connected(0, 1) is True
    assert uf.connected(0, 2) is False
    assert uf.num_components == 5
    assert uf.get_component_size(0) == 2

    # Merge {1, 2} -> component becomes {0, 1, 2}
    assert uf.union(1, 2) is True
    assert uf.connected(0, 2) is True
    assert uf.num_components == 4
    assert uf.get_component_size(2) == 3

    # Redundant connection (cycle detection test)
    assert uf.union(0, 2) is False  # Already connected!
    assert uf.num_components == 4

    # Merge {3, 4} and {4, 5}
    assert uf.union(3, 4) is True
    assert uf.union(4, 5) is True
    assert uf.num_components == 2

    # Final bridge between {0, 1, 2} and {3, 4, 5}
    assert uf.union(2, 5) is True
    assert uf.num_components == 1
    assert uf.max_component_size == 6
    assert uf.connected(0, 5) is True

    print("✅ All UnionFind tests passed successfully!")


if __name__ == "__main__":
    test_union_find()

Switch:  [ 7 ] [ 6 ] [ 5 ] [ 4 ] [ 3 ] [ 2 ] [ 1 ] [ 0 ]
State:     0     0     1     0     1     0     0     1
Meaning:        (Heater)       (Garage)            (Front Door)

# 1. Test if k-th bit is set (0-indexed from right)
is_set = (x >> k) & 1 == 1

# 2. Set k-th bit to 1
x |= (1 << k)

# 3. Clear k-th bit to 0
x &= ~(1 << k)

# 4. Toggle k-th bit (0 -> 1, 1 -> 0)
x ^= (1 << k)

# 5. Clear lowest set bit (Brian Kernighan's trick)
x &= (x - 1)  # e.g., 01100 -> 01000

# 6. Isolate lowest set bit
lowest = x & (-x)  # e.g., 01100 -> 00100

# 7. Check if x is a power of 2
is_pow2 = x > 0 and (x & (x - 1)) == 0

# 1. Brian Kernighan's Algorithm: Count Set Bits (Hamming Weight)
# Runs in O(Set Bits) time, NOT O(32) — skips all 0-bits instantly!
def count_set_bits(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # Clears rightmost 1-bit
        count += 1
    return count


# 2. Single Number (XOR Cancellation) — O(N) Time, O(1) Space
# Given an array where every element appears twice except one:
def single_number(nums: list[int]) -> int:
    unique = 0
    for x in nums:
        unique ^= x  # x ^ x = 0; 0 ^ unique = unique
    return unique

"""
Production Bit Manipulation Library.
Includes Brian Kernighan popcount, two non-repeating numbers, and submask iterator.
"""

from typing import Iterator, List, Tuple

class BitHacks:
    """Production suite of silicon-level bit manipulation algorithms."""

    @staticmethod
    def count_set_bits(n: int) -> int:
        """Counts set bits using Brian Kernighan's algorithm in O(K) where K = set bits."""
        count = 0
        while n > 0:
            n &= (n - 1)
            count += 1
        return count

    @staticmethod
    def two_single_numbers(nums: List[int]) -> Tuple[int, int]:
        """Finds the two unique numbers in an array where all other elements appear twice.

        Time: O(N)
        Space: O(1)
        """
        # Step 1: XOR all elements -> gives xor_all = a ^ b
        xor_all = 0
        for x in nums:
            xor_all ^= x

        # Step 2: Find any bit where a and b differ (isolate lowest set bit)
        diff_bit = xor_all & (-xor_all)

        # Step 3: Partition all numbers into two groups based on diff_bit
        a = b = 0
        for x in nums:
            if x & diff_bit:
                a ^= x
            else:
                b ^= x

        return (min(a, b), max(a, b))

    @staticmethod
    def enumerate_submasks(mask: int) -> Iterator[int]:
        """Iterates through all submasks of a given mask in descending order.

        Complexity:
            Iterating over submasks of all masks takes O(3^N) total time, not O(4^N)!
        """
        sub = mask
        while sub > 0:
            yield sub
            sub = (sub - 1) & mask
        yield 0  # Empty submask

# ❌ BUG: Evaluates as 1 << (2 + 1) = 1 << 3 = 8!
   val = 1 << 2 + 1

   # ✅ FIX: Explicit parentheses
   val = (1 << 2) + 1  # Equals 5

# ❌ BUG: Evaluates as x & (1 == 0) -> x & False -> 0!
   if x & 1 == 0: ...

   # ✅ FIX: Always wrap bitwise expressions in parentheses!
   if (x & 1) == 0: ...

MASK_32 = 0xFFFFFFFF
   val_32 = x & MASK_32

def popcount_32(x: int) -> int:
    """Computes number of set bits in a 32-bit int in 5 clock cycles using SWAR."""
    x = x - ((x >> 1) & 0x55555555)  # Sum 2-bit pairs
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)  # Sum 4-bit nibbles
    x = (x + (x >> 4)) & 0x0F0F0F0F  # Sum 8-bit bytes
    x = x + (x >> 8)  # Sum 16-bit words
    x = x + (x >> 16)  # Sum 32-bit full register
    return x & 0x0000003F

sub = mask
while sub:
    sub = (sub - 1) & mask

DE_BRUIJN_LOOKUP = [
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
]

def floor_log2(v: int) -> int:
    """Returns floor(log2(v)) in 3 operations without branches or loops."""
    # Round down to power of 2
    v |= v >> 1
    v |= v >> 2
    v |= v >> 4
    v |= v >> 8
    v |= v >> 16
    v = (v >> 1) + 1
    # Multiply by De Bruijn constant and shift
    return DE_BRUIJN_LOOKUP[(v * 0x077CB531 & 0xFFFFFFFF) >> 27]

from typing import Iterator, List, Tuple


def count_set_bits(n: int) -> int:
    """Counts set bits using Brian Kernighan's algorithm.

    Complexity: O(K) where K is number of set bits (skips zero bits entirely).
    """
    count = 0
    while n > 0:
        n &= (n - 1)
        count += 1
    return count


def is_power_of_two(n: int) -> bool:
    """Determines whether n is a positive power of 2 in O(1) time."""
    return n > 0 and (n & (n - 1)) == 0


def single_number(nums: List[int]) -> int:
    """Finds the single unique number where all others appear twice.

    Complexity: O(N) time, O(1) space.
    """
    unique = 0
    for x in nums:
        unique ^= x
    return unique


def two_single_numbers(nums: List[int]) -> Tuple[int, int]:
    """Finds the two unique numbers where all others appear twice.

    Complexity: O(N) time, O(1) space.
    """
    xor_all = 0
    for x in nums:
        xor_all ^= x

    # Isolate lowest set bit where a and b differ
    diff_bit = xor_all & (-xor_all)

    a = b = 0
    for x in nums:
        if x & diff_bit:
            a ^= x
        else:
            b ^= x

    return (min(a, b), max(a, b))


def enumerate_submasks(mask: int) -> List[int]:
    """Enumerates all submasks of a mask in descending order."""
    submasks: List[int] = []
    sub = mask
    while sub > 0:
        submasks.append(sub)
        sub = (sub - 1) & mask
    submasks.append(0)
    return submasks


def test_bit_manipulation() -> None:
    """Unit tests verifying bit manipulation functions."""
    # 1. Brian Kernighan count set bits
    assert count_set_bits(0) == 0
    assert count_set_bits(1) == 1
    assert count_set_bits(7) == 3   # 0b111
    assert count_set_bits(16) == 1  # 0b10000
    assert count_set_bits(255) == 8 # 0b11111111

    # 2. Power of two check
    assert is_power_of_two(1) is True
    assert is_power_of_two(2) is True
    assert is_power_of_two(16) is True
    assert is_power_of_two(18) is False
    assert is_power_of_two(0) is False
    assert is_power_of_two(-8) is False

    # 3. Single Number
    assert single_number([4, 1, 2, 1, 2]) == 4
    assert single_number([2, 2, 1]) == 1

    # 4. Two Single Numbers
    assert two_single_numbers([1, 2, 1, 3, 2, 5]) == (3, 5)
    assert two_single_numbers([-1, 0]) == (-1, 0)

    # 5. Submask enumeration
    # mask = 0b101 = 5. Submasks: 5 (101), 4 (100), 1 (001), 0 (000)
    assert enumerate_submasks(5) == [5, 4, 1, 0]

    print("✅ All Bit Manipulation tests passed successfully!")


if __name__ == "__main__":
    test_bit_manipulation()

N = 8 nodes → 7 edges
(Count the arrows in the diagram above: 1→2, 1→3, 2→4, 2→5, 3→6, 4→7, 4→8 = 7 ✅)

Tree(root=1)
├── Tree(root=2)
│   ├── Tree(root=4)
│   │   ├── Tree(root=7) → Empty, Empty
│   │   └── Tree(root=8) → Empty, Empty
│   └── Tree(root=5) → Empty, Empty
└── Tree(root=3)
    └── Tree(root=6) → Empty, Empty

Tree:          Array (0-indexed):
     1          [1, 2, 3, 4, 5, 6, 7]
   /   \         0  1  2  3  4  5  6
  2     3
 / \ / \
4  5 6  7

Parent of index 3 (value=4): ⌊(3-1)/2⌋ = 1 → value=2 ✅
Left child of index 1 (value=2): 2(1)+1 = 3 → value=4 ✅
Right child of index 1 (value=2): 2(1)+2 = 4 → value=5 ✅

# Heap array navigation in Python
def parent(i):     return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i):return 2 * i + 2

from __future__ import annotations
from typing import Optional

class TreeNode:
    """Standard LeetCode-style binary tree node."""
    def __init__(self, val: int = 0,
                 left: Optional[TreeNode] = None,
                 right: Optional[TreeNode] = None):
        self.val   = val
        self.left  = left
        self.right = right

    def __repr__(self) -> str:
        return f"TreeNode({self.val})"


# Build the tree:   1
#                  / \
#                 2   3
#                / \
#               4   5
root = TreeNode(1,
    left=TreeNode(2,
        left=TreeNode(4),
        right=TreeNode(5)),
    right=TreeNode(3))

def height(node: Optional[TreeNode]) -> int:
    """Recursive height. O(N) time, O(H) space."""
    if not node:
        return -1  # Convention: empty tree has height -1; leaf has height 0
    return 1 + max(height(node.left), height(node.right))

def count_nodes(node: Optional[TreeNode]) -> int:
    """Count all nodes. O(N) time."""
    if not node:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

def is_leaf(node: TreeNode) -> bool:
    return node.left is None and node.right is None

Queue: [1]           → Process 1. Add children 2, 3.
Queue: [2, 3]        → Process 2. Add children 4, 5.
Queue: [3, 4, 5]     → Process 3. Add children 6, 7.
Queue: [4, 5, 6, 7]  → Process 4. Add children 8, 9.
Queue: [5, 6, 7, 8, 9] → Process 5. No children.
...and so on

from collections import deque
from typing import Optional

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    """Returns nodes grouped by level. O(N) time, O(W) space (W = max width)."""
    if not root:
        return []
    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)     # ← KEY: snapshot of current level's size
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(current_level)

    return result
# → [[1], [2,3], [4,5,6,7], [8,9]]

def pre_order_recursive(root: Optional[TreeNode]) -> list[int]:
    """Root → Left → Right. O(N) time, O(H) space."""
    result = []
    def dfs(node):
        if not node: return
        result.append(node.val)  # ① Process ROOT first
        dfs(node.left)           # ② Then LEFT subtree
        dfs(node.right)          # ③ Then RIGHT subtree
    dfs(root)
    return result

def pre_order_iterative(root: Optional[TreeNode]) -> list[int]:
    if not root: return []
    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push RIGHT first so LEFT is processed first (LIFO)
        if node.right: stack.append(node.right)
        if node.left:  stack.append(node.left)

    return result

def in_order_recursive(root: Optional[TreeNode]) -> list[int]:
    """Left → Root → Right. Yields SORTED output for BST. O(N) time, O(H) space."""
    result = []
    def dfs(node):
        if not node: return
        dfs(node.left)           # ① Dive ALL the way LEFT first
        result.append(node.val)  # ② Process ROOT (when left is done)
        dfs(node.right)          # ③ Then RIGHT subtree
    dfs(root)
    return result

def in_order_iterative(root: Optional[TreeNode]) -> list[int]:
    result = []
    stack  = []
    curr   = root

    while curr or stack:
        # Go as far LEFT as possible — push every node
        while curr:
            stack.append(curr)
            curr = curr.left

        # Backtrack: process the node
        curr = stack.pop()
        result.append(curr.val)

        # Now explore its RIGHT subtree
        curr = curr.right

    return result

def post_order_recursive(root: Optional[TreeNode]) -> list[int]:
    """Left → Right → Root. Bottom-up computation. O(N) time, O(H) space."""
    result = []
    def dfs(node):
        if not node: return
        dfs(node.left)           # ① LEFT subtree first
        dfs(node.right)          # ② RIGHT subtree second
        result.append(node.val)  # ③ Process ROOT LAST
    dfs(root)
    return result

in_order(2)
  │
  ├─► in_order(1)              ← Dive LEFT
  │     ├─► in_order(None)     ← Hit bottom, return
  │     ├─► PROCESS: append 1  ← ✅ Visit 1
  │     └─► in_order(None)     ← No right child, return
  │
  ├─► PROCESS: append 2        ← ✅ Visit 2 (after left subtree done)
  │
  └─► in_order(3)              ← Dive RIGHT
        ├─► in_order(None)     ← Hit bottom, return
        ├─► PROCESS: append 3  ← ✅ Visit 3
        └─► in_order(None)     ← No right child, return

Final result: [1, 2, 3] ← SORTED! ✅

from typing import Generator, Optional

def in_order_gen(node: Optional[TreeNode]) -> Generator[int, None, None]:
    """Lazy in-order traversal using generators. O(H) space at any moment."""
    if node:
        yield from in_order_gen(node.left)
        yield node.val
        yield from in_order_gen(node.right)

# Usage: only materializes one value at a time
for val in in_order_gen(root):
    if val == target:
        break  # Stop early — we don't need to traverse the rest!

def search(root, target):
    curr = root
    while curr:
        if target == curr.val:   return True   # Found!
        elif target < curr.val:  curr = curr.left   # Go LEFT
        else:                    curr = curr.right  # Go RIGHT
    return False  # Fell off the tree — not found

At 50: 60 > 50 → go RIGHT
At 70: 60 < 70 → go LEFT
At 60: 60 == 60 → FOUND! ✅
(Only visited 3 nodes out of 7)

def insert(root, val):
    if not root:
        return TreeNode(val)  # Base case: empty spot found
    if val < root.val:
        root.left  = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    # If val == root.val, ignore duplicates (or handle as needed)
    return root

At 50: 45 < 50 → go LEFT
At 30: 45 > 30 → go RIGHT
At 40: 45 > 40 → go RIGHT
At None: INSERT 45 here as right child of 40 ✅

def delete(root, val):
    if not root: return None

    if val < root.val:
        root.left  = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        # Found the node to delete!
        if not root.left:  return root.right  # Case 1 or 2 (no left child)
        if not root.right: return root.left   # Case 2 (no right child)

        # Case 3: Two children — find in-order successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val   = successor.val             # Copy successor's value
        root.right = delete(root.right, successor.val)  # Delete successor

    return root

1. Find in-order successor of 50: min of right subtree {70, 60, 80}
   → Go right to 70, then go left to 60. 60 has no left child.
   → In-order successor = 60

2. Copy 60 into root's val. Tree root now holds value 60.

3. Delete 60 from right subtree:
   → 60 is a leaf there. Remove it.

Result: Root = 60, left subtree unchanged, right = {70, 80}

In-order traversal of BST  ↔  Sorted array
BST insertion              ↔  Inserting into sorted array at correct position
BST search                 ↔  Binary search on sorted array
BST height                 ↔  log(N) iterations of binary search

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    """Check if tree satisfies BST property at every node."""
    if not root: return True
    if not (min_val < root.val < max_val): return False
    return (is_valid_bst(root.left,  min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))

def kth_smallest(root, k):
    """In-order traversal stops at the k-th element. O(H + k) time."""
    count = [0]
    result = [None]

    def in_order(node):
        if not node or result[0] is not None: return
        in_order(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        in_order(node.right)

    in_order(root)
    return result[0]

def lca_bst(root, p, q):
    """The BST property makes LCA trivial. O(H) time."""
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left   # Both nodes are in left subtree
        elif p.val > root.val and q.val > root.val:
            root = root.right  # Both nodes are in right subtree
        else:
            return root  # We've diverged — this is the LCA!

balance_factor(node) = height(left subtree) − height(right subtree)

# Option 1: sortedcontainers (pip install sortedcontainers)
from sortedcontainers import SortedList, SortedDict, SortedSet

sl = SortedList([5, 1, 3, 2, 4])
sl.add(0)           # O(log N)
sl.remove(3)        # O(log N)
sl[0]               # O(log N) — smallest element
sl.bisect_left(3)   # O(log N) — index of first element >= 3
# SortedList supports slicing: sl[2:5] is O(log N + k)

# Option 2: Use heapq for partial ordered access (only min/max)
import heapq
heap = [5, 1, 3, 2, 4]
heapq.heapify(heap)     # O(N)
heapq.heappush(heap, 0) # O(log N)
heapq.heappop(heap)     # O(log N) — always removes minimum

# Option 3: Use bisect for sorted list (no automatic rebalancing)
import bisect
arr = [1, 2, 4, 5]
bisect.insort(arr, 3)   # O(N) — but correct sorted insertion position is O(log N) to find