Intermediate Examples

"""Example 25: A Doubling Dynamic Array -- Amortized O(1) Append, Counted."""
 
# list.append is amortized O(1) because resizes DOUBLE capacity (co-02):
# rare, expensive O(n) copies are outweighed by many cheap O(1) appends in
# between. This example implements that doubling explicitly and COUNTS copies.
 
 
class DynamicArray:  # => a from-scratch array that grows by doubling, like CPython's
    def __init__(self) -> None:
        self.capacity: int = 1  # => starts with room for exactly 1 element
        self.size: int = 0  # => how many elements are actually stored so far
        self.data: list[int | None] = [None] * self.capacity  # => the backing storage
        self.total_copies: int = 0  # => running count of element copies during resizes
 
    def append(self, value: int) -> None:  # => amortized O(1) per call
        if self.size == self.capacity:  # => backing storage is full -- must grow
            self._resize(self.capacity * 2)  # => DOUBLING is what makes this amortized
        self.data[self.size] = value  # => O(1): writes into the next free slot
        self.size += 1  # => one more element stored
 
    def _resize(self, new_capacity: int) -> None:  # => O(n): the rare, expensive step
        new_data: list[int | None] = [None] * new_capacity  # => a fresh, larger array
        for i in range(self.size):  # => copies every EXISTING element over
            new_data[i] = self.data[i]  # => one copy per existing element
            self.total_copies += 1  # => tallies this copy for the amortized-cost check
        self.data = new_data  # => the array now points at the larger backing storage
        self.capacity = new_capacity  # => capacity reflects the new, larger size
 
 
arr = DynamicArray()  # => starts empty, capacity 1
n = 1000  # => how many appends to perform
for i in range(n):  # => n appends -- MOST are O(1), a few trigger an O(n) resize
    arr.append(i)  # => amortized O(1) each
 
average_copies_per_append = arr.total_copies / n  # => the amortized cost per append
print(arr.size)  # => Output: 1000
print(arr.total_copies)  # => Output: 1023 -- sum of 1+2+4+...+512, just over n
print(f"{average_copies_per_append:.3f}")  # => Output: 1.023
 
assert arr.size == n  # => confirms every append landed correctly
assert (
    average_copies_per_append < 2.0
)  # => confirms the amortized cost stays BOUNDED by a small constant, not O(n)
print("ex-25 OK")  # => Output: ex-25 OK

1000
1023
1.023
ex-25 OK

"""Example 25: pytest verification for the Doubling Dynamic Array."""
 
from example import DynamicArray
 
 
def test_all_appended_values_are_stored_in_order() -> None:
    arr = DynamicArray()
    for v in [10, 20, 30]:
        arr.append(v)
    assert arr.size == 3
    assert [arr.data[i] for i in range(arr.size)] == [10, 20, 30]
 
 
def test_amortized_copy_count_stays_bounded_as_n_grows() -> None:
    small = DynamicArray()
    for i in range(100):
        small.append(i)
    large = DynamicArray()
    for i in range(10_000):
        large.append(i)
    small_ratio = small.total_copies / 100
    large_ratio = large.total_copies / 10_000
    assert large_ratio < 2.0  # => a 100x bigger n does NOT proportionally grow copies
    assert small_ratio < 2.0
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 26: The Accounting Method -- Credits That Never Go Negative."""
 
# The accounting method (co-02) charges each operation a fixed AMORTIZED cost
# (here, 3 credits per append), banking the surplus over what the operation
# actually spends. A resize later "cashes in" that banked surplus to pay for
# copying every existing element -- the proof this works is that the credit
# balance never dips below zero, across the ENTIRE sequence of operations.
 
 
class AccountedArray:  # => a doubling array instrumented to track its credit ledger
    def __init__(self) -> None:
        self.capacity: int = 1  # => starts with room for 1 element
        self.size: int = 0  # => elements actually stored
        self.credit_balance: int = 0  # => the running amortized-credit ledger
 
    def append(self, value: int) -> None:  # => charges 3, an amortized O(1) cost
        actual_cost = 1  # => the baseline cost: writing one new element
        if self.size == self.capacity:  # => full -- a resize must happen first
            actual_cost += self.size  # => ALSO pays 1 per existing element it copies
            self.capacity *= 2  # => doubles capacity, same as Example 25
        self.credit_balance += 3  # => charges this append the fixed amortized rate
        self.credit_balance -= actual_cost  # => pays for whatever actually happened
        assert (
            self.credit_balance >= 0
        )  # => THE PROOF: banked credit always covers the real cost
        self.size += 1  # => one more element now stored
 
 
arr = AccountedArray()  # => starts empty
balances: list[int] = []  # => records the credit balance after every single append
for i in range(500):  # => 500 appends -- several of them trigger a doubling resize
    arr.append(i)  # => charges 3, pays the real cost, asserts balance >= 0 internally
    balances.append(arr.credit_balance)  # => snapshots the balance for inspection
 
print(min(balances))  # => Output: 2 -- the balance dips low but never below zero
print(arr.credit_balance)  # => Output: 489 -- the final leftover credit
print(arr.size)  # => Output: 500
 
assert min(balances) >= 0  # => confirms the balance NEVER went negative, at any point
assert arr.size == 500  # => confirms every append actually landed
print("ex-26 OK")  # => Output: ex-26 OK

2
489
500
ex-26 OK

"""Example 26: pytest verification for the Accounting Method."""
 
from example import AccountedArray
 
 
def test_credit_balance_never_goes_negative_across_many_resizes() -> None:
    arr = AccountedArray()
    for i in range(2000):  # => several doublings happen along the way
        arr.append(i)
        assert arr.credit_balance >= 0  # => re-checked after every single append
 
 
def test_final_size_matches_number_of_appends() -> None:
    arr = AccountedArray()
    for i in range(37):  # => a deliberately non-power-of-two count
        arr.append(i)
    assert arr.size == 37
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 27: Randomized-Pivot Quicksort -- Sorted Input No Longer Degrades."""
 
# Example 8's naive quicksort always picks the FIRST element, so sorted input
# triggers its O(n^2) worst case. Picking a RANDOM pivot each time (co-08)
# makes that worst case astronomically unlikely -- expected O(n log n) even
# on already-sorted input, because the bad case no longer depends on the DATA.
import random
 
comparisons = 0  # => a global counter, reset before each measurement below
 
 
def randomized_quicksort(items: list[int], lo: int = 0, hi: int | None = None) -> None:
    global comparisons  # => this function mutates the module-level counter
    if hi is None:  # => top-level call defaults hi to the last index
        hi = len(items) - 1  # => sorts the WHOLE list on the first call
    if lo < hi:  # => base case: 0 or 1 elements need no partitioning
        p = random_pivot_partition(items, lo, hi)  # => the only change from Example 8
        randomized_quicksort(items, lo, p - 1)  # => recurses on the left partition
        randomized_quicksort(items, p + 1, hi)  # => recurses on the right partition
 
 
def random_pivot_partition(items: list[int], lo: int, hi: int) -> int:
    global comparisons  # => mutates the shared counter
    rand_index = random.randint(lo, hi)  # => picks a UNIFORMLY random index as pivot
    items[rand_index], items[lo] = (  # => opens the swap-to-front tuple assignment
        items[lo],  # => the old first element moves to the random index's old slot
        items[rand_index],  # => the randomly chosen value moves to the front
    )  # => swaps it to the front so the rest of the logic is unchanged
    pivot = items[lo]  # => now behaves exactly like Example 8's first-pivot partition
    i = lo  # => boundary of the "<pivot" region
    for j in range(lo + 1, hi + 1):  # => scans every element after the pivot
        comparisons += 1  # => counts this one comparison against the pivot
        if items[j] < pivot:  # => belongs strictly before the pivot
            i += 1  # => grows the "<pivot" region
            items[i], items[j] = items[j], items[i]  # => swaps it in
    items[lo], items[i] = items[i], items[lo]  # => places the pivot at its final spot
    return i  # => pivot's final index
 
 
random.seed(99)  # => fixed seed -- makes the "random" pivot choices reproducible
n = 500  # => how many elements to sort
already_sorted: list[int] = list(  # => opens the pre-sorted input construction
    range(n)  # => builds 0, 1, 2, ..., n-1 in ascending order
)  # => Example 8's worst case: pre-sorted input
naive_worst_case = n * (n - 1) // 2  # => what Example 8 would score on this same input
comparisons = 0  # => resets the shared counter before measuring
randomized_quicksort(already_sorted)  # => sorts the SAME kind of worst-case input
print(comparisons < naive_worst_case)  # => Output: True
print(already_sorted == list(range(n)))  # => Output: True -- still sorts correctly
 
assert (  # => opens the check -- wraps the long boolean across two lines
    comparisons < naive_worst_case  # => True only if randomization avoided the blow-up
)  # => confirms randomization avoids the O(n^2) sorted-input trap
assert already_sorted == list(range(n))  # => confirms correctness is unaffected
print("ex-27 OK")  # => Output: ex-27 OK

True
True
ex-27 OK

"""Example 27: pytest verification for Randomized-Pivot Quicksort."""
 
import random
 
import example
 
 
def test_sorted_input_no_longer_hits_the_naive_worst_case() -> None:
    random.seed(3)
    n = 300
    data: list[int] = list(range(n))
    example.comparisons = 0
    example.randomized_quicksort(data)
    naive_worst_case = n * (n - 1) // 2
    assert example.comparisons < naive_worst_case  # => far below the O(n^2) bound
    assert data == list(range(n))  # => still correctly sorted
 
 
def test_matches_sorted_on_random_input() -> None:
    random.seed(4)
    data: list[int] = random.sample(range(1000), 60)
    expected = sorted(data)
    example.randomized_quicksort(data)
    assert data == expected
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 28: Quickselect -- the k-th Smallest Element in Expected O(n)."""
 
# Quickselect (co-08) reuses quicksort's partition step, but RECURSES INTO
# ONLY ONE SIDE -- whichever side contains the k-th position -- instead of
# both, giving expected O(n) instead of a full O(n log n) sort.
import random
 
 
def quickselect(  # => recurses into only the side containing rank k, not both sides
    items: list[int],  # => the array to search within (never mutated by the caller)
    k: int,  # => k is the 0-indexed target rank to find
) -> int:  # => returns the k-th smallest (0-indexed)
    working = list(items)  # => a copy -- the caller's list is never mutated
    lo, hi = 0, len(working) - 1  # => the active search range, shrinks each round
    while True:  # => each iteration eliminates one whole side of the partition
        if lo == hi:  # => only one candidate remains -- it must be the answer
            return working[lo]  # => base case: nowhere left to search
        p = random_pivot_partition(working, lo, hi)  # => the pivot's final sorted index
        if p == k:  # => the pivot itself landed exactly at the target rank
            return working[p]  # => found it -- no more recursion needed
        if p < k:  # => the k-th smallest is somewhere to the RIGHT of the pivot
            lo = p + 1  # => discards the entire left side -- it's already too small
        else:  # => the k-th smallest is somewhere to the LEFT of the pivot
            hi = p - 1  # => discards the entire right side -- it's already too big
 
 
def random_pivot_partition(
    items: list[int], lo: int, hi: int
) -> int:  # => Lomuto scheme
    rand_index = random.randint(lo, hi)  # => a uniformly random pivot choice
    items[rand_index], items[lo] = items[lo], items[rand_index]  # => moves it to front
    pivot = items[lo]  # => the value being partitioned around
    i = lo  # => boundary of the "<pivot" region
    for j in range(lo + 1, hi + 1):  # => scans the rest of the active range
        if items[j] < pivot:  # => belongs strictly before the pivot
            i += 1  # => grows the "<pivot" region by one slot
            items[i], items[j] = items[j], items[i]  # => swaps it into place
    items[lo], items[i] = items[i], items[lo]  # => places the pivot at its final index
    return i  # => the pivot's final, correctly-sorted-position index
 
 
# a fixed seed makes this whole demo fully reproducible across runs
random.seed(17)  # => fixed seed -> reproducible pivot choices
data: list[int] = random.sample(range(1000), 40)  # => 40 distinct random ints
sorted_data = sorted(data)  # => ground truth to check quickselect against
third_smallest = quickselect(data, k=2)  # => 0-indexed: k=2 means the 3rd smallest
median = quickselect(data, k=len(data) // 2)  # => the middle element by rank
print(third_smallest == sorted_data[2])  # => Output: True
print(median == sorted_data[len(data) // 2])  # => Output: True
 
assert third_smallest == sorted_data[2]  # => confirms rank-2 matches sorted()[2]
assert median == sorted_data[len(data) // 2]  # => confirms the median rank matches too
assert quickselect(data, k=0) == min(data)  # => rank 0 is always the minimum
assert quickselect(data, k=len(data) - 1) == max(data)  # => the last rank is the max
print("ex-28 OK")  # => Output: ex-28 OK

True
True
ex-28 OK

"""Example 28: pytest verification for Quickselect."""
 
import random
 
from example import quickselect
 
 
def test_every_rank_matches_sorted_index() -> None:
    random.seed(6)
    data: list[int] = random.sample(range(500), 25)
    expected = sorted(data)
    for k in range(len(data)):  # => checks EVERY rank, not just a couple samples
        assert quickselect(data, k) == expected[k]
 
 
def test_does_not_mutate_the_caller_list() -> None:
    data: list[int] = [5, 2, 8, 1]
    original = list(data)
    quickselect(data, k=1)
    assert data == original  # => the caller's list is untouched
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 29: Closest Pair of Points -- Divide and Conquer vs Brute Force."""
 
# Divide-and-conquer (co-06) beats brute force's O(n^2) by SPLITTING points on
# x, solving each half recursively, then only re-checking a thin vertical
# STRIP near the midline for cross-half pairs -- overall O(n log n).
# Squared distances (int, no sqrt) are compared throughout -- ordering is
# identical to true distance, but no floating-point rounding risk.
 
Point = tuple[int, int]  # => a 2D point as (x, y)
 
 
def squared_distance(p: Point, q: Point) -> int:  # => (dx^2 + dy^2), no sqrt needed
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2  # => squared Euclidean distance
 
 
def brute_force_closest_pair(points: list[Point]) -> int:  # => O(n^2): every pair
    best = squared_distance(points[0], points[1])  # => a starting baseline
    for i in range(len(points)):  # => tries every unordered pair once
        for j in range(i + 1, len(points)):  # => avoids re-checking the same pair twice
            best = min(best, squared_distance(points[i], points[j]))  # => tracks min
    return best  # => the true minimum squared distance, by exhaustive comparison
 
 
def closest_pair_divide_conquer(points: list[Point]) -> int:  # => O(n log n) overall
    by_x = sorted(points, key=lambda p: p[0])  # => O(n log n), done once up front
    return _closest_pair(by_x)  # => delegates to the recursive divide step
 
 
def _closest_pair(points_by_x: list[Point]) -> int:  # => points, already sorted by x
    n = len(points_by_x)  # => how many points remain in this recursive slice
    if n <= 3:  # => base case: brute force is cheap enough for 3 or fewer points
        return brute_force_closest_pair(points_by_x)  # => O(1) work at this size
    mid = n // 2  # => the split point
    mid_x = points_by_x[mid][0]  # => the x-coordinate of the dividing line
    left_best = _closest_pair(points_by_x[:mid])  # => recurses on the left half
    right_best = _closest_pair(points_by_x[mid:])  # => recurses on the right half
    best = min(left_best, right_best)  # => the best purely-within-one-half distance
    strip = [  # => opens the filtered "close to the midline" list comprehension
        p
        for p in points_by_x
        if (p[0] - mid_x) ** 2 < best  # => squared-x pruning
    ]  # => points close enough to the midline to possibly beat `best`
    strip.sort(key=lambda p: p[1])  # => sorting the (small) strip by y enables pruning
    for i in range(len(strip)):  # => checks each strip point against its NEAR neighbors
        for j in range(  # => opens the bounded inner-neighbor range
            i + 1,
            min(i + 8, len(strip)),  # => caps the scan at 7 neighbors, never n
        ):  # => a well-known bound: at most 7 useful neighbors in y-sorted order
            best = min(best, squared_distance(strip[i], strip[j]))  # => updates best
    return best  # => the true minimum squared distance across the whole point set
 
 
points: list[Point] = [  # => opens the 8-point set, deliberately mixing close/far pairs
    (2, 3),  # => part of the TRUE closest pair, alongside (3, 4)
    (12, 30),  # => far from the cluster near the origin
    (40, 50),  # => the most distant outlier point
    (5, 1),  # => moderately close to the origin cluster
    (12, 10),  # => sits between the near cluster and the mid-distance points
    (3, 4),  # => the other half of the TRUE closest pair, alongside (2, 3)
    (0, 0),  # => the origin -- anchors the near cluster
    (20, 20),  # => a mid-distance point, closer to the outliers than the cluster
]  # => 8 points, deliberately mixing close and far pairs
brute_answer = brute_force_closest_pair(points)  # => O(n^2) ground truth
fast_answer = closest_pair_divide_conquer(points)  # => O(n log n) divide-and-conquer
print(brute_answer)  # => Output: 2
print(fast_answer)  # => Output: 2
 
assert brute_answer == fast_answer  # => confirms both approaches agree exactly
assert brute_answer == squared_distance(  # => opens the explicit ground-truth check
    (2, 3),
    (3, 4),  # => the two points expected to be the closest pair
)  # => confirms (2,3)-(3,4) is genuinely the closest pair: dist^2 = 1+1 = 2
print("ex-29 OK")  # => Output: ex-29 OK

2
2
ex-29 OK

"""Example 29: pytest verification for Closest Pair Divide and Conquer."""
 
import random
 
from example import brute_force_closest_pair, closest_pair_divide_conquer
 
 
def test_matches_brute_force_on_random_points() -> None:
    random.seed(31)
    points = [
        (random.randint(0, 200), random.randint(0, 200)) for _ in range(40)
    ]  # => 40 random 2D points
    assert closest_pair_divide_conquer(points) == brute_force_closest_pair(points)
 
 
def test_matches_brute_force_on_a_small_collinear_set() -> None:
    points = [(0, 0), (1, 0), (5, 0), (9, 0)]  # => all on one line -- an edge shape
    assert closest_pair_divide_conquer(points) == brute_force_closest_pair(points)
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 30: Fenwick Tree (Binary Indexed Tree) -- O(log n) Prefix Sum + Update."""
 
# A Fenwick tree (co-14) stores partial sums keyed by the LOWEST SET BIT of
# each index -- both point-update and prefix-sum become O(log n), beating a
# plain array's O(n) prefix-sum recompute and a running-array's O(n) update-shift.
 
 
class FenwickTree:  # => 1-indexed internally -- index 0 is unused, by convention
    def __init__(self, n: int) -> None:  # => allocates a zeroed tree sized for n items
        self.n = n  # => the number of elements this tree covers
        self.tree: list[int] = [0] * (n + 1)  # => tree[i] holds a partial-sum range
 
    def update(self, i: int, delta: int) -> None:  # => O(log n): adds delta at index i
        i += 1  # => converts the caller's 0-indexed position to 1-indexed internally
        while i <= self.n:  # => climbs toward the root, following the BIT structure
            self.tree[i] += delta  # => applies delta to this partial-sum node
            i += i & (-i)  # => jumps to the next node this index's range feeds into
            # => `i & (-i)` isolates the lowest set bit -- the core BIT trick
 
    def prefix_sum(  # => walks DOWN the BIT structure, accumulating partial sums
        self,  # => the tree instance holding this Fenwick array
        i: int,  # => the (0-indexed) inclusive upper bound of the prefix
    ) -> int:  # => O(log n): sum of elements [0, i] inclusive
        i += 1  # => converts to 1-indexed
        total = 0  # => accumulates the running sum
        while i > 0:  # => walks DOWN toward index 0, following the BIT structure
            total += self.tree[i]  # => adds this node's partial sum
            i -= i & (-i)  # => strips the lowest set bit, moving to the parent range
        return total  # => the sum of all elements from index 0 through i, inclusive
 
    def range_sum(self, lo: int, hi: int) -> int:  # => O(log n): sum of [lo, hi]
        if lo == 0:  # => no need to subtract anything below index 0
            return self.prefix_sum(hi)  # => the prefix sum IS the range sum
        return self.prefix_sum(hi) - self.prefix_sum(  # => two O(log n) lookups
            lo - 1  # => excludes everything strictly below lo
        )  # => classic prefix-sum subtraction trick
 
 
values: list[int] = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2]  # => 10 starting values
n = len(values)  # => n = 10
fenwick = FenwickTree(n)  # => starts as all zeros
for idx, v in enumerate(values):  # => O(n log n) total: one update per starting value
    fenwick.update(idx, v)  # => builds up the tree to reflect `values`
 
running_array = list(values)  # => a plain array, kept in sync for cross-checking
print(fenwick.prefix_sum(4))  # => Output: 15 -- sum of values[0..4]
print(sum(running_array[: 4 + 1]))  # => Output: 15 -- confirms the plain-array sum
 
fenwick.update(2, 10)  # => adds 10 AT index 2 (a point update, not a set)
running_array[2] += 10  # => keeps the plain array in sync for comparison
print(fenwick.prefix_sum(4))  # => Output: 25 -- 15 + 10, reflecting the point update
print(fenwick.range_sum(3, 7))  # => Output: 15 -- sum of values[3..7] after the update
 
assert (  # => opens the Fenwick-vs-plain-sum cross-check
    fenwick.prefix_sum(4)
    == sum(  # => cross-checks the Fenwick tree vs a plain sum
        running_array[: 4 + 1]  # => the same [0, 4] slice, summed the naive O(n) way
    )  # => closes the naive prefix sum call
)  # => confirms Fenwick matches a plain re-sum after the update
assert (  # => opens the arbitrary-range cross-check
    fenwick.range_sum(3, 7)
    == sum(  # => cross-checks an arbitrary mid-range sum
        running_array[3 : 7 + 1]  # => the same [3, 7] slice, summed the naive O(n) way
    )  # => closes the naive range sum call
)  # => confirms arbitrary range sums match too
print("ex-30 OK")  # => Output: ex-30 OK

15
15
25
15
ex-30 OK

"""Example 30: pytest verification for the Fenwick Tree."""
 
import random
 
from example import FenwickTree
 
 
def test_matches_a_running_array_after_random_updates() -> None:
    random.seed(41)
    n = 30
    running: list[int] = [0] * n
    fenwick = FenwickTree(n)
    for _ in range(100):  # => 100 random point updates
        idx = random.randint(0, n - 1)
        delta = random.randint(-5, 5)
        fenwick.update(idx, delta)
        running[idx] += delta
        lo = random.randint(0, n - 1)
        hi = random.randint(lo, n - 1)
        assert fenwick.range_sum(lo, hi) == sum(running[lo : hi + 1])
 
 
def test_prefix_sum_of_all_zeros_is_zero() -> None:
    fenwick = FenwickTree(5)
    assert fenwick.prefix_sum(4) == 0  # => nothing has been added yet
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 31: Segment Tree -- O(log n) Range-Minimum Queries."""
 
# A segment tree (co-15) stores, at each internal node, the aggregate (here,
# the MIN) of an entire array range -- built once in O(n), then answering any
# range-min query in O(log n) by combining O(log n) precomputed sub-ranges.
 
INF = float(  # => opens the sentinel construction
    "inf"  # => Python's built-in way to spell positive infinity as a float
)  # => the segment tree's "empty range" sentinel, larger than any value
 
 
class SegmentTreeMin:  # => a segment tree specialized for range-minimum queries
    def __init__(self, data: list[int]) -> None:  # => O(n): builds the whole tree once
        self.n = len(data)  # => the number of leaf elements
        self.tree: list[float] = [INF] * (  # => opens the array-backed tree allocation
            4 * self.n  # => 4n is a standard safe upper bound on array-based tree size
        )  # => 4n is a standard safe upper bound on array-based tree size
        self._build(data, 1, 0, self.n - 1)  # => builds the tree rooted at index 1
 
    def _build(  # => recursively fills every node with its range's minimum, bottom-up
        self,  # => the tree instance under construction
        data: list[int],  # => the source array being indexed
        node: int,  # => this call's own array-backed tree index
        lo: int,  # => the low end of this call's range
        hi: int,  # => [lo, hi] is this call's range
    ) -> (  # => the return-type annotation, split across lines
        None  # => mutates self.tree in place -- nothing to return
    ):  # => node uses the implicit-heap array encoding: children 2*node, 2*node+1
        if lo == hi:  # => a leaf: exactly one array element
            self.tree[node] = data[lo]  # => stores that element's own value directly
            return  # => nothing more to combine at a leaf
        mid = (lo + hi) // 2  # => splits this range roughly in half
        self._build(data, 2 * node, lo, mid)  # => builds the left child (index 2*node)
        self._build(  # => opens the right-child build call
            data,  # => the same source array, threaded through
            2 * node + 1,  # => the right child's own tree index
            mid + 1,  # => one past the left child's range
            hi,  # => builds the right child (2*node+1)
        )  # => closes the right-child build call
        self.tree[node] = min(  # => this node's value is the min of its two children
            self.tree[2 * node],  # => left child's own min
            self.tree[2 * node + 1],  # => right child's own min
        )  # => combines children into this node's own min
 
    def query(self, lo: int, hi: int) -> float:  # => O(log n): min over [lo, hi]
        # => the public entry point -- always starts recursion at node 1, full range
        return self._query(1, 0, self.n - 1, lo, hi)  # => starts the recursion at root
 
    def _query(  # => the classic three-way split: outside, inside, or partial overlap
        self,  # => the tree instance being queried
        node: int,  # => this call's own array-backed tree index
        node_lo: int,  # => this node's range's low end
        node_hi: int,  # => this node's range's high end
        lo: int,  # => the query range's low end
        hi: int,  # => node covers [node_lo, node_hi]
    ) -> float:  # => the query range [lo, hi] never changes across the recursion
        if hi < node_lo or node_hi < lo:  # => this node's range is entirely OUTSIDE
            return INF  # => contributes nothing to a min -- INF is the identity
        if lo <= node_lo and node_hi <= hi:  # => this node's range is entirely INSIDE
            return self.tree[node]  # => the precomputed min covers this whole range
        mid = (node_lo + node_hi) // 2  # => this node PARTIALLY overlaps -- must split
        return min(  # => combines whatever both children individually contribute
            self._query(  # => opens the left-half recursive call
                2 * node,  # => the left child's own tree index
                node_lo,  # => left child's range starts where this node's did
                mid,  # => left child's range ends at the midpoint
                lo,  # => the query range's low end, passed through unchanged
                hi,  # => recurses into the left half
            ),  # => closes the left-half recursive call
            self._query(  # => opens the right-half recursive call
                2 * node + 1,  # => the right child's own tree index
                mid + 1,  # => right child's range starts just past the midpoint
                node_hi,  # => right child's range ends where this node's did
                lo,  # => the query range's low end, passed through unchanged
                hi,  # => and the right half
            ),  # => closes the right-half recursive call
        )  # => combines whatever both halves contribute
 
 
# => 8 unsorted integers, min is 1 at index 3
data: list[int] = [  # => opens the source-array literal
    5,  # => index 0
    2,  # => index 1
    8,  # => index 2
    1,  # => index 3 -- the global minimum
    9,  # => index 4
    3,  # => index 5
    7,  # => index 6
    4,  # => index 7
]  # => closes the source-array literal
tree = SegmentTreeMin(data)  # => O(n): builds the tree once
 
print(tree.query(0, 3))  # => Output: 1 -- min of [5, 2, 8, 1]
print(tree.query(4, 7))  # => Output: 3 -- min of [9, 3, 7, 4]
print(tree.query(0, 7))  # => Output: 1 -- min of the whole array
 
assert tree.query(0, 3) == min(data[0:4])  # => confirms against a brute-force slice min
assert tree.query(4, 7) == min(data[4:8])  # => confirms another range against a slice
# => a single-element range is the INSIDE case -- returns the leaf's own value directly
assert tree.query(2, 2) == data[2]  # => a single-element range returns that element
print("ex-31 OK")  # => Output: ex-31 OK

1
3
1
ex-31 OK

"""Example 31: pytest verification for Segment Tree Range-Min."""
 
import random
 
from example import SegmentTreeMin
 
 
def test_matches_brute_force_slice_min_on_random_ranges() -> None:
    random.seed(51)
    data = [random.randint(-50, 50) for _ in range(25)]
    tree = SegmentTreeMin(data)
    for _ in range(60):
        lo = random.randint(0, len(data) - 1)
        hi = random.randint(lo, len(data) - 1)
        assert tree.query(lo, hi) == min(data[lo : hi + 1])
 
 
def test_whole_array_query_matches_python_min() -> None:
    data = [4, -2, 9, 0, 7]
    tree = SegmentTreeMin(data)
    assert tree.query(0, len(data) - 1) == min(data)
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 32: Segment Tree with Lazy Range-Add -- O(log n) Range Update, Point Read."""
 
# A plain segment tree's range update is O(n) (touch every leaf). LAZY
# propagation (co-15) defers that work: a fully-covered node just stamps a
# pending "add" tag and stops -- the tag only gets PUSHED DOWN to children
# when a later query actually needs to look inside that node. O(log n) both ways.
 
 
class LazySegmentTree:  # => sum-tracking tree with O(log n) range-add, point query
    def __init__(self, data: list[int]) -> None:  # => O(n): builds the initial tree
        self.n = len(data)  # => number of leaf elements
        self.tree: list[int] = [0] * (4 * self.n)  # => tree[node] = sum over its range
        self.lazy: list[int] = [0] * (4 * self.n)  # => pending, not-yet-pushed adds
        self._build(data, 1, 0, self.n - 1)  # => builds the initial tree, O(n)
 
    def _build(  # => bottom-up: leaves first, then each parent sums its two children
        self,  # => the tree instance under construction
        data: list[int],  # => the source array being indexed
        node: int,  # => this call's own array-backed tree index
        lo: int,  # => the low end of this node's range
        hi: int,  # => [lo, hi] is this node's range
    ) -> None:  # => fills self.tree over the array-index encoding, no lazy tags yet
        if lo == hi:  # => leaf: exactly one element
            self.tree[node] = data[lo]  # => its own starting value
            return  # => nothing more to combine at a leaf
        mid = (lo + hi) // 2  # => splits the range
        self._build(data, 2 * node, lo, mid)  # => builds the left child
        self._build(data, 2 * node + 1, mid + 1, hi)  # => builds the right child
        self.tree[node] = (  # => opens the parent-sum assignment
            self.tree[2 * node]  # => the left child's own sum
            + self.tree[2 * node + 1]  # => plus the right child's own sum
        )  # => this node's sum is its children's combined sum
 
    def _push_down(  # => flushes node's pending tag one level down, THEN clears it
        self,  # => the tree instance being flushed
        node: int,  # => this call's own array-backed tree index
        lo: int,  # => the low end of this node's range
        hi: int,  # => node's own [lo, hi] range
    ) -> None:  # => flushes a pending tag
        if self.lazy[node] == 0:  # => nothing pending -- nothing to push
            return  # => an early exit avoids touching children unnecessarily
        mid = (lo + hi) // 2  # => needed to size each child's range
        for child, child_lo, child_hi in (  # => opens the (index, lo, hi) pair loop
            (2 * node, lo, mid),  # => the left child's index and range
            (2 * node + 1, mid + 1, hi),  # => the right child's index and range
        ):  # => applies the SAME pending delta to both children
            self.tree[child] += self.lazy[node] * (  # => scales the delta by range size
                child_hi - child_lo + 1  # => how many elements this child's range spans
            )  # => scales by range SIZE, since tree[] stores a SUM, not a single value
            self.lazy[child] += self.lazy[node]  # => the child inherits the pending tag
        self.lazy[node] = 0  # => this node's tag has now been fully passed down
 
    def range_add(  # => public entry point -- the only method callers use to update
        self,  # => the tree instance being updated
        lo: int,  # => the low end of the range to add to
        hi: int,  # => the high end of the range to add to
        delta: int,  # => adds delta to every index in [lo, hi]
    ) -> None:  # => O(log n): adds delta
        self._range_add(1, 0, self.n - 1, lo, hi, delta)  # => starts at the root
 
    def _range_add(  # => the classic outside/inside/partial-overlap recursive split
        self,  # => the tree instance being updated
        node: int,  # => this call's own array-backed tree index
        node_lo: int,  # => this node's range's low end
        node_hi: int,  # => this node's range's high end
        lo: int,  # => the update range's low end
        hi: int,  # => the update range's high end
        delta: int,  # => node covers [node_lo, node_hi]
    ) -> None:  # => mutates self.tree and self.lazy in place, returns nothing
        if hi < node_lo or node_hi < lo:  # => this node's range is entirely outside
            return  # => nothing to do here
        if lo <= node_lo and node_hi <= hi:  # => this node's range is entirely inside
            self.tree[node] += delta * (  # => the aggregate sum shifts by delta * count
                node_hi - node_lo + 1  # => how many elements this whole node covers
            )  # => updates the aggregate sum directly
            self.lazy[node] += delta  # => defers pushing to children until needed
            return  # => THE LAZY PART: children are not touched yet
        self._push_down(  # => must resolve any pending tag before recursing further
            node,  # => this node's own array-backed tree index
            node_lo,  # => this node's own range low end
            node_hi,  # => flushes THIS node's own stale tag first
        )  # => must resolve any pending tag before recursing further
        mid = (node_lo + node_hi) // 2  # => splits this node's range for the recursion
        self._range_add(2 * node, node_lo, mid, lo, hi, delta)  # => recurses left
        self._range_add(2 * node + 1, mid + 1, node_hi, lo, hi, delta)  # => and right
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]  # => recombines
 
    def point_query(self, i: int) -> int:  # => O(log n): the CURRENT value at index i
        return self._point_query(1, 0, self.n - 1, i)  # => starts at the root
 
    def _point_query(  # => descends one side at each level, pushing down tags first
        self,  # => the tree instance being queried
        node: int,  # => this call's own array-backed tree index
        lo: int,  # => this node's range's low end
        hi: int,  # => this node's range's high end
        i: int,  # => node covers [lo, hi]; i is the target
    ) -> int:  # => returns the up-to-date value at index i
        if lo == hi:  # => a leaf -- its stored sum IS the single element's value
            return self.tree[node]  # => already reflects every applied range-add
        self._push_down(  # => resolves any pending tag before descending further
            node,  # => this node's own array-backed tree index
            lo,  # => this node's own range low end
            hi,  # => this node's own range, needed to size its children
        )  # => resolves any pending tag before descending further
        mid = (lo + hi) // 2  # => decides which child holds index i
        if i <= mid:  # => the target index lives in the left half
            return self._point_query(2 * node, lo, mid, i)  # => recurses left
        return self._point_query(2 * node + 1, mid + 1, hi, i)  # => lives in the right
 
 
data: list[int] = [1, 2, 3, 4, 5, 6]  # => 6 starting values
tree = LazySegmentTree(data)  # => O(n): builds the initial tree
tree.range_add(1, 4, 10)  # => O(log n): adds 10 to every element in indices [1, 4]
 
expected: list[int] = [  # => opens the hand-computed plain-array result
    1,  # => index 0 -- outside [1, 4], unchanged
    12,  # => index 1 -- 2 + 10
    13,  # => index 2 -- 3 + 10
    14,  # => index 3 -- 4 + 10
    15,  # => index 4 -- 5 + 10
    6,  # => index 5 -- outside [1, 4], unchanged
]  # => the plain-array result of the same range-add, computed by hand
for i in range(len(data)):  # => reads every index back through the tree
    print(f"index {i}: {tree.point_query(i)}")  # => Output: index N: value, per index
    assert tree.point_query(i) == expected[i]  # => confirms each point read is correct
 
tree.range_add(0, 2, 5)  # => a SECOND, overlapping range-add, to stack lazy tags
expected2: list[int] = [6, 17, 18, 14, 15, 6]  # => reflects both range-adds combined
for i in range(len(data)):  # => re-reads every index after the second update
    assert tree.point_query(i) == expected2[i]  # => confirms overlapping updates stack
print("ex-32 OK")  # => Output: ex-32 OK

index 0: 1
index 1: 12
index 2: 13
index 3: 14
index 4: 15
index 5: 6
ex-32 OK

"""Example 32: pytest verification for Lazy Range-Add Segment Tree."""
 
import random
 
from example import LazySegmentTree
 
 
def test_matches_a_brute_force_running_array_after_random_range_adds() -> None:
    random.seed(61)
    n = 20
    running: list[int] = [0] * n
    tree = LazySegmentTree(running)
    for _ in range(50):  # => 50 random overlapping range-add operations
        lo = random.randint(0, n - 1)
        hi = random.randint(lo, n - 1)
        delta = random.randint(-10, 10)
        tree.range_add(lo, hi, delta)
        for i in range(lo, hi + 1):  # => the brute-force ground truth, applied directly
            running[i] += delta
        for i in range(n):  # => re-checks every index after each update
            assert tree.point_query(i) == running[i]
 
 
def test_non_overlapping_updates_stay_independent() -> None:
    tree = LazySegmentTree([0, 0, 0, 0])
    tree.range_add(0, 1, 5)
    tree.range_add(2, 3, -3)
    assert [tree.point_query(i) for i in range(4)] == [5, 5, -3, -3]
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 33: Union-Find with Union-by-Rank and Path Compression."""
 
# Two independent optimizations on top of Example 22's plain union-find
# (co-16): UNION-BY-RANK always attaches the shorter tree under the taller
# one, keeping trees flat; PATH COMPRESSION flattens every node visited
# during find() to point directly at the root. Together they give amortized
# O(alpha(n)) per operation -- alpha is the inverse Ackermann function, which
# is under 5 for any n that could ever be represented in memory: effectively
# constant time in practice, though not literally O(1) in the strict sense.
 
 
class OptimizedUnionFind:  # => union-find with both classic optimizations applied
    def __init__(self, n: int) -> None:  # => n singleton groups, each its own root
        self.parent: list[int] = list(  # => opens the initial parent-list construction
            range(n)  # => index i's parent starts as i itself -- n separate groups
        )  # => each element starts as its own root
        self.rank: list[int] = [0] * n  # => an upper bound on each tree's height
 
    def find(self, x: int) -> int:  # => amortized O(alpha(n)) with path compression
        if self.parent[x] != x:  # => x is not yet its own group's root
            self.parent[x] = (
                self.find(  # => recurses first, THEN repoints on the way back
                    self.parent[
                        x
                    ]  # => climbs toward the root through x's current parent
                )  # => closes the recursive find() call
            )  # => PATH COMPRESSION: recurses to the root, then repoints x DIRECTLY at it
        return self.parent[x]  # => x's parent is now either itself, or the true root
 
    def union(self, a: int, b: int) -> None:  # => amortized O(alpha(n))
        root_a = self.find(a)  # => a's group root (path-compressed along the way)
        root_b = self.find(b)  # => b's group root
        if root_a == root_b:  # => already the same group -- nothing to merge
            return  # => a union with itself is a no-op
        if (  # => opens the rank comparison
            self.rank[root_a] < self.rank[root_b]
        ):  # => UNION BY RANK: shorter under taller
            self.parent[root_a] = (  # => opens the shorter-under-taller reassignment
                root_b  # => attaches the shorter tree under the taller
            )  # => closes the reassignment
        elif self.rank[root_a] > self.rank[root_b]:  # => the mirror comparison
            self.parent[root_b] = root_a  # => the mirror case
        else:  # => equal rank -- pick either, and the result grows one level taller
            self.parent[root_b] = root_a  # => arbitrarily attaches b's root under a's
            self.rank[root_a] += 1  # => only NOW does the resulting tree's height grow
 
 
def total_find_depth(  # => a diagnostic helper -- NOT part of the union-find API itself
    uf: OptimizedUnionFind,  # => the union-find structure being queried
    n: int,  # => the structure to measure, and its element count
) -> int:  # => sums parent-hop counts
    total = 0  # => accumulates hops across every element's find()
    for x in range(n):  # => checks every element once
        depth = 0  # => counts hops from x up to its root
        cur = (
            x  # => a local walker, so find()'s own compression isn't re-triggered here
        )
        while (
            uf.parent[cur] != cur
        ):  # => climbs until reaching a self-parent (the root)
            cur = uf.parent[cur]  # => one hop toward the root
            depth += 1  # => tallies this hop
        total += depth  # => adds this element's hop count to the running total
    return total  # => the sum of all n elements' current depths
 
 
# => margin note: n stays large enough that even O(n) depth would be visible
n = 1000  # => a reasonably large element count, to make near-flat trees visible
uf = OptimizedUnionFind(n)  # => n singleton groups
for i in range(  # => opens the union-count range
    n - 1  # => one union per consecutive pair -- n-1 total union calls
):  # => chains everything into ONE big group, worst-case union order
    uf.union(i, i + 1)  # => unions consecutive elements, one after another
 
for x in range(n):  # => forces every element's find() to run and compress its path
    uf.find(x)  # => after this loop, EVERY element points close to directly at the root
 
average_depth = (  # => opens the average-hops-per-element computation
    total_find_depth(uf, n) / n  # => total hops divided by the element count
)  # => average remaining hops after compression
print(average_depth < 3.0)  # => Output: True -- effectively flat, not O(n) deep
print(uf.find(0) == uf.find(n - 1))  # => Output: True -- all n elements are one group
 
# => without path compression, this 1000-element CHAIN union order would leave average
# => depth near n/2 -- the near-flat result below is entirely due to the optimizations
assert (  # => opens the near-flat-depth check
    average_depth < 3.0  # => True only if the optimizations actually kept trees flat
)  # => confirms near-constant depth despite a 1000-element chain
assert uf.find(0) == uf.find(n - 1)  # => confirms the whole chain merged into one group
print("ex-33 OK")  # => Output: ex-33 OK

True
True
ex-33 OK

"""Example 33: pytest verification for Optimized Union-Find."""
 
from example import OptimizedUnionFind
 
 
def test_path_compression_keeps_trees_shallow_after_a_worst_case_chain() -> None:
    n = 500
    uf = OptimizedUnionFind(n)
    for i in range(n - 1):
        uf.union(i, i + 1)  # => the worst possible union order for a naive union-find
    for x in range(n):
        uf.find(x)  # => compresses every path
    for x in range(n):  # => re-checks: every element's parent should now be near-root
        assert uf.parent[x] == uf.find(x) or uf.parent[x] == uf.parent[uf.find(x)]
 
 
def test_connectivity_after_optimized_unions_matches_expectations() -> None:
    uf = OptimizedUnionFind(6)
    uf.union(0, 1)
    uf.union(2, 3)
    uf.union(1, 2)  # => merges {0,1} and {2,3} into one group of 4
    assert uf.find(0) == uf.find(3)  # => transitively connected
    assert uf.find(0) != uf.find(4)  # => 4 and 5 remain their own singleton groups
    assert uf.find(4) != uf.find(5)
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 34: Count Connected Components via Union-Find."""
 
# Union every edge's two endpoints (co-16), and each surviving DISTINCT root
# afterward identifies one connected component -- no traversal needed at all,
# just a pass over the edges followed by counting unique find() results.
 
 
class UnionFind:  # => the optimized version from Example 33, reused as-is
    def __init__(self, n: int) -> None:  # => n singleton groups, each its own root
        self.parent: list[int] = list(  # => opens the initial parent-array construction
            range(n)  # => index i's parent starts as i itself -- n separate groups
        )  # => each element starts as its own root
        self.rank: list[int] = [0] * n  # => an upper bound on each tree's height
 
    def find(self, x: int) -> int:  # => amortized O(alpha(n)) with path compression
        if self.parent[x] != x:  # => x is not yet its own group's root
            self.parent[x] = (
                self.find(  # => recurses first, THEN repoints on the way back
                    self.parent[
                        x  # => the element whose root is being sought
                    ]  # => climbs toward the root through x's current parent
                )  # => closes the recursive find() call
            )  # => path-compresses on the way back
        return self.parent[x]  # => x's parent is now either itself, or the true root
 
    def union(self, a: int, b: int) -> None:  # => amortized O(alpha(n))
        root_a, root_b = self.find(a), self.find(b)  # => both groups' roots, compressed
        if root_a == root_b:  # => already the same group -- nothing to merge
            return  # => a union with itself is a no-op
        if (  # => opens the shorter-under-taller rank comparison
            self.rank[root_a] < self.rank[root_b]  # => a's tree is strictly shorter
        ):  # => UNION BY RANK: shorter under taller
            self.parent[root_a] = (  # => opens the shorter-under-taller reassignment
                root_b  # => attaches the shorter tree under the taller
            )  # => closes the reassignment
        elif self.rank[root_a] > self.rank[root_b]:  # => the mirror comparison
            self.parent[root_b] = root_a  # => the mirror case
        else:  # => equal rank -- pick either, and the result grows one level taller
            self.parent[root_b] = root_a  # => arbitrarily attaches b's root under a's
            self.rank[root_a] += 1  # => only NOW does the resulting tree's height grow
 
 
def count_components(  # => no traversal at all -- just union every edge, then count roots
    n: int,  # => the number of nodes, labeled 0..n-1
    edges: list[tuple[int, int]],  # => n nodes labeled 0..n-1, plus the edge list
) -> int:  # => O((V+E) alpha(V))
    uf = UnionFind(n)  # => n nodes, each initially its own component
    for a, b in edges:  # => O(E): unions every edge's endpoints
        uf.union(a, b)  # => merges a's and b's components, if not already merged
    roots = {  # => opens the set-comprehension collecting distinct roots
        uf.find(x)  # => the compressed root of node x
        for x in range(n)  # => a set automatically discards duplicate roots
    }  # => O(V): the set of DISTINCT surviving roots
    return len(roots)  # => one component per distinct root
 
 
n = 8  # => 8 nodes, labeled 0..7
edges: list[  # => opens the edge-list type annotation
    tuple[int, int]  # => each edge is a pair of node indices
] = [  # => opens the edge list -- deliberately leaves node 7 isolated
    (0, 1),  # => connects 0 and 1 into one group
    (1, 2),  # => extends that group to include 2 -- {0, 1, 2}
    (3, 4),  # => a separate two-node group -- {3, 4}
    (5, 6),  # => another separate two-node group -- {5, 6}
]  # => leaves 7 fully isolated
component_count = count_components(n, edges)  # => how many separate groups exist
print(component_count)  # => Output: 4 -- {0,1,2}, {3,4}, {5,6}, {7}
 
assert component_count == 4  # => confirms the four expected groups
assert count_components(5, []) == 5  # => no edges at all: every node is its own group
assert count_components(3, [(0, 1), (1, 2)]) == 1  # => a fully connected chain
print("ex-34 OK")  # => Output: ex-34 OK

4
ex-34 OK

"""Example 34: pytest verification for Connected Components via Union-Find."""
 
from example import count_components
 
 
def test_disconnected_pairs_and_a_singleton() -> None:
    assert count_components(8, [(0, 1), (1, 2), (3, 4), (5, 6)]) == 4
 
 
def test_fully_connected_graph_has_one_component() -> None:
    edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
    assert count_components(5, edges) == 1
 
 
def test_no_edges_means_every_node_is_its_own_component() -> None:
    assert count_components(4, []) == 4
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 35: Topological Sort via Kahn's Algorithm."""
 
# Kahn's algorithm (co-18) repeatedly removes nodes with IN-DEGREE ZERO --
# nodes with no remaining unprocessed prerequisites -- appending each to the
# result and decrementing its neighbors' in-degrees, until none remain.
from collections import deque  # => O(1) popleft, unlike a plain list
 
 
def kahn_topological_sort(  # => BFS-style: repeatedly peel off zero-in-degree nodes
    graph: dict[str, list[str]],  # => adjacency map: node -> list of nodes it points to
) -> list[str] | None:  # => None if a cycle makes ordering impossible
    in_degree: dict[str, int] = {  # => opens the initial all-zero in-degree map
        node: 0 for node in graph
    }  # => starts every node's in-degree at 0
    for node in graph:  # => O(V+E): counts how many edges point INTO each node
        for neighbor in graph[
            node  # => this node's own outgoing edges
        ]:  # => each outgoing edge increments the target's count
            in_degree[neighbor] += 1  # => one more prerequisite for neighbor
 
    queue: deque[str] = deque(  # => opens the initial ready-queue construction
        [node for node in graph if in_degree[node] == 0]  # => the zero-in-degree nodes
    )  # => nodes with NO prerequisites can go first
    order: list[str] = []  # => accumulates the resulting topological order
    while queue:  # => processes nodes in waves of "everything now unblocked"
        node = queue.popleft()  # => O(1): the next ready node
        order.append(node)  # => it has no remaining unprocessed prerequisites
        for neighbor in graph[node]:  # => "removes" node by decrementing its neighbors
            in_degree[neighbor] -= 1  # => one fewer prerequisite for neighbor
            if in_degree[neighbor] == 0:  # => neighbor is now fully unblocked
                queue.append(neighbor)  # => schedules it for the next wave
 
    if len(order) != len(graph):  # => fewer nodes than expected means a CYCLE exists
        return None  # => a cycle prevents any valid topological order
    return order  # => a valid topological order: every edge points forward in the list
 
 
graph: dict[str, list[str]] = {  # => a small build-dependency DAG
    "compile": ["link"],  # => must happen before "link"
    "link": ["test"],  # => must happen before "test"
    "fetch_deps": ["compile"],  # => the true starting point -- no prerequisites at all
    "test": [],  # => the terminal step -- nothing depends on it
}  # => closes the dependency map -- 4 build steps, one linear chain
order = kahn_topological_sort(graph)  # => a valid build order
print(order)  # => Output: ['fetch_deps', 'compile', 'link', 'test']
 
assert order is not None  # => confirms no cycle was detected
position = {  # => opens the node -> index lookup, built from the result order
    node: i  # => this node's position within the final order
    for i, node in enumerate(order)  # => pairs each node with its position
}  # => node -> its index in the order
assert position["fetch_deps"] < position["compile"]  # => a dependency comes first
assert position["compile"] < position["link"]  # => confirms edge direction is honored
assert position["link"] < position["test"]  # => confirms the last edge too
print("ex-35 OK")  # => Output: ex-35 OK

['fetch_deps', 'compile', 'link', 'test']
ex-35 OK

"""Example 35: pytest verification for Kahn's Topological Sort."""
 
from example import kahn_topological_sort
 
 
def test_every_edge_points_forward_in_the_resulting_order() -> None:
    graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
    order = kahn_topological_sort(graph)
    assert order is not None
    position = {node: i for i, node in enumerate(order)}
    for u, neighbors in graph.items():
        for v in neighbors:
            assert position[u] < position[v]  # => u always precedes v
 
 
def test_a_valid_dag_produces_a_full_length_order() -> None:
    graph = {"x": ["y"], "y": ["z"], "z": []}
    order = kahn_topological_sort(graph)
    assert order is not None
    assert len(order) == 3
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 36: Topological Sort via DFS Finish-Time Ordering."""
 
# A DFS-based topological sort (co-18, co-17) is the mirror image of Kahn's
# algorithm: run DFS, and REVERSE the order nodes FINISH in. A node finishes
# only after every node reachable from it has already finished -- so it must
# come before all of them in a valid ordering.
 
 
def dfs_topological_sort(  # => reverse of DFS finish order -- the mirror of Kahn's
    graph: dict[str, list[str]],  # => adjacency map: node -> list of nodes it points to
) -> list[str]:  # => assumes a DAG -- no cycle check here (that's Example 37)
    visited: set[str] = set()  # => nodes already fully explored
    finish_order: list[  # => opens the type annotation split across lines
        str
    ] = []  # => nodes appended in the order they FINISH, not start
 
    def recurse(node: str) -> None:  # => a standard recursive DFS visit
        visited.add(node)  # => marks node as being explored
        for neighbor in graph.get(node, []):  # => visits every outgoing edge
            if neighbor not in visited:  # => only recurse into undiscovered nodes
                recurse(neighbor)  # => fully explores neighbor before returning
        finish_order.append(node)  # => node is appended ONLY after ALL its descendants
 
    for node in graph:  # => handles disconnected pieces too, not just one component
        if node not in visited:  # => starts a fresh DFS from any unvisited node
            recurse(node)  # => explores this whole component
 
    return list(reversed(finish_order))  # => REVERSING finish order gives topo order
 
 
graph: dict[str, list[str]] = {  # => the same build-dependency DAG as Example 35
    "compile": ["link"],  # => must happen before "link"
    "link": ["test"],  # => must happen before "test"
    "fetch_deps": ["compile"],  # => the true starting point -- no prerequisites at all
    "test": [],  # => the terminal step -- nothing depends on it
}  # => closes the dependency map -- same 4 build steps as Example 35
order = dfs_topological_sort(graph)  # => a valid build order, via DFS this time
print(order)  # => Output: ['fetch_deps', 'compile', 'link', 'test']
 
position = {node: i for i, node in enumerate(order)}  # => node -> its index in order
assert (  # => opens the first edge-direction check
    position["fetch_deps"] < position["compile"]  # => True iff "fetch_deps" comes first
)  # => confirms edge direction honored
assert position["compile"] < position["link"]  # => confirms another edge's direction
assert position["link"] < position["test"]  # => confirms the last edge too
assert len(order) == len(graph)  # => confirms every node appears exactly once
print("ex-36 OK")  # => Output: ex-36 OK

['fetch_deps', 'compile', 'link', 'test']
ex-36 OK

"""Example 36: pytest verification for DFS-Based Topological Sort."""
 
from example import dfs_topological_sort
 
 
def test_every_edge_points_forward_in_the_resulting_order() -> None:
    graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
    order = dfs_topological_sort(graph)
    position = {node: i for i, node in enumerate(order)}
    for u, neighbors in graph.items():
        for v in neighbors:
            assert position[u] < position[v]
 
 
def test_handles_a_disconnected_graph_with_two_components() -> None:
    graph = {"a": ["b"], "b": [], "x": ["y"], "y": []}
    order = dfs_topological_sort(graph)
    assert set(order) == {"a", "b", "x", "y"}  # => every node from both components
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 37: Detect a Cycle in a Directed Graph via DFS Coloring."""
 
# THREE colors (co-17, co-18), not just visited/unvisited, are what makes
# cycle detection possible: WHITE (unseen), GRAY (on the CURRENT recursion
# path), BLACK (fully finished). A back edge to a GRAY node means the current
# path loops back on itself -- exactly what a cycle is.
from enum import Enum, auto  # => Color is an Enum, not a bare string, for type safety
 
 
class Color(Enum):  # => three DFS visitation states -- enables cycle detection
    WHITE = auto()  # => not yet discovered
    GRAY = auto()  # => currently on the recursion stack -- an ANCESTOR of this call
    BLACK = auto()  # => fully explored, off the recursion stack
 
 
def has_cycle(  # => three-color DFS: a GRAY-to-GRAY edge means a back edge, i.e. a cycle
    graph: dict[str, list[str]],  # => adjacency map: node -> list of nodes it points to
) -> bool:  # => True iff a directed cycle exists
    color: dict[str, Color] = {  # => opens the dict-comprehension initializing colors
        node: Color.WHITE  # => every node begins undiscovered
        for node in graph  # => every node starts undiscovered
    }  # => all start WHITE
 
    def recurse(node: str) -> bool:  # => True if a cycle is found reachable from node
        color[node] = Color.GRAY  # => node is now an ANCESTOR on this recursion path
        for neighbor in graph.get(node, []):  # => tries every outgoing edge
            if color[neighbor] == Color.GRAY:  # => THE TELLTALE SIGN: an edge back to
                return True  # => an ancestor still on the stack -- a genuine cycle
            if color[
                neighbor  # => this neighbor's current visitation state
            ] == Color.WHITE and recurse(  # => only recurse into unseen nodes
                neighbor  # => the unvisited neighbor to explore next
            ):  # => explore unseen nodes
                return True  # => a cycle was found deeper in this branch
        color[node] = Color.BLACK  # => node is fully explored -- no longer an ancestor
        return False  # => no cycle found through this node
 
    return any(  # => True as soon as ANY unvisited component reports a cycle
        recurse(node)  # => explores each still-undiscovered component
        for node in graph
        if color[node] == Color.WHITE
    )  # => checks every component
 
 
acyclic_graph: dict[  # => opens the type annotation split across lines
    str, list[str]  # => same node/neighbor-list shape as every other graph example
] = {  # => a valid DAG -- Examples 35/36's build order
    "fetch_deps": ["compile"],  # => the true starting point -- no prerequisites at all
    "compile": ["link"],  # => must happen before "link"
    "link": ["test"],  # => must happen before "test"
    "test": [],  # => the terminal step -- nothing depends on it
}  # => closes the acyclic dependency map -- same DAG as Examples 35/36
cyclic_graph: dict[str, list[str]] = {  # => the SAME shape, but with one edge reversed
    "fetch_deps": ["compile"],  # => still the nominal starting point
    "compile": ["link"],  # => still points forward to "link"
    "link": ["test", "fetch_deps"],  # => "link" points back to "fetch_deps" -- a cycle
    "test": [],  # => still a terminal step, uninvolved in the cycle
}  # => closes the cyclic dependency map -- one back edge creates fetch_deps->compile->link->fetch_deps
print(has_cycle(acyclic_graph))  # => Output: False
print(has_cycle(cyclic_graph))  # => Output: True
 
assert (  # => opens the "acyclic graph correctly accepted" check
    has_cycle(acyclic_graph) is False  # => True only if no cycle was falsely detected
)  # => confirms a valid DAG is correctly accepted
assert has_cycle(cyclic_graph) is True  # => confirms the cycle is correctly detected
assert has_cycle({"a": ["a"]}) is True  # => a self-loop is the smallest possible cycle
print("ex-37 OK")  # => Output: ex-37 OK

False
True
ex-37 OK

"""Example 37: pytest verification for Directed Cycle Detection."""
 
from example import has_cycle
 
 
def test_dag_reports_no_cycle() -> None:
    graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
    assert has_cycle(graph) is False
 
 
def test_cyclic_graph_reports_a_cycle() -> None:
    graph = {"a": ["b"], "b": ["c"], "c": ["a"]}  # => a -> b -> c -> a
    assert has_cycle(graph) is True
 
 
def test_disconnected_dag_with_no_cycle_reports_false() -> None:
    graph = {"a": ["b"], "b": [], "x": ["y"], "y": []}
    assert has_cycle(graph) is False
 
 
# => Run: pytest -- Output: 3 passed

3 passed

"""Example 38: Dijkstra's Shortest Paths with a heapq Priority Queue."""
 
# Dijkstra (co-19) greedily expands the CHEAPEST-known frontier node next,
# using a min-heap (co-09) to find that node in O(log n) instead of an O(n)
# linear scan. Requires NON-NEGATIVE edge weights -- Example 40 shows why.
import heapq  # => the min-heap priority queue used to pick the cheapest frontier node
 
 
def dijkstra(  # => greedily finalizes the cheapest-known frontier node each iteration
    graph: dict[str, list[tuple[str, int]]],  # => node -> list of (neighbor, weight)
    start: str,  # => weighted adjacency + origin
) -> dict[str, float]:  # => node -> shortest distance from start
    distances: dict[str, float] = {  # => opens the initial all-infinity distance map
        node: float("inf")  # => every node starts unreachable, by default
        for node in graph  # => every node starts unreachable
    }  # => everyone starts at infinity
    distances[start] = 0  # => the start node is trivially 0 away from itself
    heap: list[
        tuple[float, str]  # => (distance, node) pairs, ordered by distance
    ] = [  # => opens the initial single-entry priority queue
        (0, start)  # => the only known reachable node at distance 0
    ]  # => (distance, node) -- heapq sorts by distance
    visited: set[str] = set()  # => nodes whose shortest distance is FINAL
    while heap:  # => processes the frontier until nothing remains
        dist, node = heapq.heappop(heap)  # => the currently cheapest unfinalized node
        if node in visited:  # => a stale heap entry -- a shorter path already finalized
            continue  # => skip it, no new information here
        visited.add(node)  # => node's distance is now FINAL -- never improves further
        for neighbor, weight in graph[node]:  # => relaxes every outgoing edge
            new_dist = dist + weight  # => the cost of reaching neighbor THROUGH node
            if new_dist < distances[neighbor]:  # => a strictly better path was found
                distances[neighbor] = new_dist  # => records the improved distance
                heapq.heappush(heap, (new_dist, neighbor))  # => schedules the candidate
    return distances  # => shortest distance to every node reachable from start
 
 
graph: dict[str, list[tuple[str, int]]] = {  # => node -> list of (neighbor, weight)
    "a": [("b", 4), ("c", 1)],  # => a's direct routes: to b (cost 4), to c (cost 1)
    "b": [("d", 1)],  # => b's only route: to d (cost 1)
    "c": [("b", 2), ("d", 5)],  # => c offers a cheaper detour to b than a's direct edge
    "d": [],  # => the terminal node -- no outgoing edges
}  # => closes the weighted adjacency map -- 4 nodes
distances = dijkstra(graph, "a")  # => shortest distances from "a" to every other node
print(distances)  # => Output: {'a': 0, 'b': 3, 'c': 1, 'd': 4}
 
assert distances["a"] == 0  # => the start node is 0 away from itself
assert distances["b"] == 3  # => a->c->b (1+2=3) beats the direct a->b edge (cost 4)
assert distances["d"] == 4  # => a->c->b->d (1+2+1=4) is the cheapest route to d
print("ex-38 OK")  # => Output: ex-38 OK

{'a': 0, 'b': 3, 'c': 1, 'd': 4}
ex-38 OK

"""Example 38: pytest verification for Dijkstra with a Heap."""
 
from example import dijkstra
 
 
def test_finds_shortest_path_through_an_indirect_route() -> None:
    graph = {
        "a": [("b", 4), ("c", 1)],
        "b": [("d", 1)],
        "c": [("b", 2), ("d", 5)],
        "d": [],
    }
    distances = dijkstra(graph, "a")
    assert distances["b"] == 3  # => indirect a->c->b beats the direct edge
 
 
def test_start_node_distance_is_zero() -> None:
    graph = {"x": [("y", 5)], "y": []}
    assert dijkstra(graph, "x")["x"] == 0
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 39: Dijkstra Reports Infinity for an Unreachable Node -- Never Crashes."""
 
# Initializing every distance to infinity BEFORE running Dijkstra (co-19)
# means a node that's never relaxed simply keeps its infinite distance --
# there's no special-case branch needed, and no risk of a KeyError or crash.
import heapq
 
 
def dijkstra(  # => identical to Example 38's implementation
    graph: dict[str, list[tuple[str, int]]],
    start: str,  # => weighted adjacency + origin
) -> dict[str, float]:  # => identical to Example 38's implementation
    distances: dict[str, float] = {  # => every node starts unreachable, by design
        node: float("inf")
        for node in graph  # => "island" gets this same sentinel too
    }  # => closes the dict-comprehension
    distances[start] = 0  # => the start node is trivially 0 away from itself
    heap: list[tuple[float, str]] = [(0, start)]  # => (distance, node) priority queue
    visited: set[str] = set()  # => nodes whose shortest distance is FINAL
    while heap:  # => processes the frontier until nothing remains
        dist, node = heapq.heappop(heap)  # => the currently cheapest unfinalized node
        if node in visited:  # => a stale heap entry -- a shorter path already finalized
            continue  # => skip it, no new information here
        visited.add(node)  # => node's distance is now FINAL -- never improves further
        for neighbor, weight in graph[node]:  # => relaxes every outgoing edge
            new_dist = dist + weight  # => the cost of reaching neighbor THROUGH node
            if new_dist < distances[neighbor]:  # => a strictly better path was found
                distances[neighbor] = new_dist  # => records the improved distance
                heapq.heappush(heap, (new_dist, neighbor))  # => schedules the candidate
    return distances  # => "island" is never touched -- stays at its initial infinity
 
 
graph: dict[str, list[tuple[str, int]]] = {  # => "island" has NO incoming edge from "a"
    "a": [("b", 2)],  # => a's only route: to b (cost 2)
    "b": [],  # => a dead end, but still reachable from "a"
    "island": [],  # => completely disconnected from "a"'s component
}  # => closes the adjacency map -- "island" is a member with zero incoming edges
distances = dijkstra(graph, "a")  # => runs Dijkstra from "a"
print(distances["a"])  # => Output: 0
print(distances["b"])  # => Output: 2
print(  # => opens the print call for the unreachable node's distance
    distances["island"]  # => still the original float("inf") sentinel
)  # => Output: inf -- never relaxed, stays at its initial value
 
assert distances["b"] == 2  # => confirms the reachable node got its correct distance
assert distances["island"] == float(  # => opens the unreachable-node check
    "inf"  # => the exact sentinel value every distance was initialized to
)  # => confirms the unreachable node reports infinity, not a crash or missing key
assert "island" in distances  # => confirms the key still exists -- no KeyError risk
print("ex-39 OK")  # => Output: ex-39 OK

0
2
inf
ex-39 OK

"""Example 39: pytest verification for Dijkstra on an Unreachable Node."""
 
import math
 
from example import dijkstra
 
 
def test_unreachable_node_reports_infinity_not_an_exception() -> None:
    graph = {"a": [("b", 1)], "b": [], "z": []}  # => z has no edge from a's component
    distances = dijkstra(graph, "a")
    assert math.isinf(distances["z"])  # => infinity, never a raised exception
 
 
def test_reachable_nodes_still_get_finite_distances() -> None:
    graph = {"a": [("b", 3)], "b": [], "z": []}
    distances = dijkstra(graph, "a")
    assert distances["b"] == 3
    assert not math.isinf(distances["b"])
 
 
# => Run: pytest -- Output: 2 passed

2 passed

"""Example 40: Bellman-Ford -- Correct Shortest Paths with Negative Edges."""
 
# Bellman-Ford (co-20) relaxes EVERY edge, V-1 times over -- slower than
# Dijkstra's O((V+E) log V), at O(V*E), but it TOLERATES negative edge
# weights, which would silently give Dijkstra's greedy heap the wrong answer.
 
 
def bellman_ford(  # => brute-force relax-every-edge, repeated V-1 times, no heap needed
    n: int,  # => the number of nodes, labeled 0..n-1
    edges: list[
        tuple[int, int, int]  # => each edge is a (from, to, weight) triple
    ],  # => (from, to, weight) triples, negatives allowed
    start: int,  # => node count, edges, origin
) -> list[float]:  # => edges: (from, to, weight); returns dist[i] for each node
    dist: list[float] = [float("inf")] * n  # => every node starts at infinity
    dist[start] = 0  # => the start node is 0 away from itself
    for _ in range(n - 1):  # => V-1 full passes -- the longest possible SIMPLE path
        for u, v, w in edges:  # => relaxes every edge, every pass
            if dist[u] + w < dist[v]:  # => found a strictly cheaper way to reach v
                dist[v] = dist[u] + w  # => updates v's distance
    return dist  # => shortest distance to every node, correct even with negative edges
 
 
n = 5  # => 5 nodes, labeled 0..4
edges: list[tuple[int, int, int]] = [  # => includes a NEGATIVE edge weight (3 -> 2, -6)
    (0, 1, 6),  # => 0 to 1, cost 6
    (0, 2, 7),  # => 0 to 2, cost 7
    (1, 2, 8),  # => 1 to 2, cost 8
    (1, 3, 5),  # => 1 to 3, cost 5
    (
        1,  # => the edge's source node
        4,  # => the edge's destination node
        -4,  # => the negative weight itself
    ),  # => 1 to 4, a NEGATIVE edge -- Dijkstra could not handle this correctly
    (2, 3, -3),  # => 2 to 3, another negative edge
    (2, 4, 9),  # => 2 to 4, cost 9
    (3, 1, -2),  # => 3 to 1, a negative edge feeding back into an earlier node
    (4, 3, 7),  # => 4 to 3, cost 7
    (4, 0, 2),  # => 4 to 0, closes a cycle back to the start -- but NOT a negative one
]  # => closes the edge list -- 10 directed edges, 3 of them negative-weight
distances = bellman_ford(n, edges, start=0)  # => shortest distances from node 0
print(distances)  # => Output: [0, 2, 7, 4, -2]
 
assert distances[0] == 0  # => the start node is 0 away from itself
assert (  # => opens the "cheaper indirect path wins" check
    distances[1] == 2
)  # => reached via 0->2->3->1 (7-3-2=2), beats the direct edge (6)
assert distances[4] == -2  # => the negative edge 1->4 pulls this distance below zero
# => a negative-weight EDGE (like 1->4 at -4) doesn't imply a negative CYCLE --
# => Bellman-Ford handles this correctly; Example 41 is what a real cycle looks like
print("ex-40 OK")  # => Output: ex-40 OK

[0, 2, 7, 4, -2]
ex-40 OK

"""Example 40: pytest verification for Bellman-Ford with Negative Edges."""
 
from example import bellman_ford
 
 
def test_matches_a_known_shortest_path_answer_with_negative_edges() -> None:
    n = 5
    edges = [
        (0, 1, 6),
        (0, 2, 7),
        (1, 2, 8),
        (1, 3, 5),
        (1, 4, -4),
        (2, 3, -3),
        (2, 4, 9),
        (3, 1, -2),
        (4, 3, 7),
        (4, 0, 2),
    ]
    distances = bellman_ford(n, edges, start=0)
    assert distances == [0, 2, 7, 4, -2]
 
 
def test_positive_only_graph_matches_a_simple_hand_computed_case() -> None:
    edges = [(0, 1, 1), (1, 2, 1), (0, 2, 5)]  # => 0->1->2 (2) beats direct 0->2 (5)
    distances = bellman_ford(3, edges, start=0)
    assert distances == [0, 1, 2]
 
 
# => Run: pytest -- Output: 2 passed