Algorithms

Chapter 24 Searching & Sorting

Linear Search

Linear search is the simplest search algorithm: start at the beginning, check every element, stop when you find the target or run out of elements. Its time complexity is O(n)—in the worst case, you examine every item.

def linear_search(arr, target):
    """Return the index of target in arr, or -1 if not found."""
    for i in range(len(arr)):      # Walk through every index
        if arr[i] == target:       # Found it?
            return i               # Return the position
    return -1                      # Exhausted the list without finding target

# Usage
tasks = ["buy groceries", "write tests", "deploy app", "review PR"]
idx = linear_search(tasks, "deploy app")
print(idx)  # 2

When is linear search the right choice? More often than you might think:

• Unsorted data—you cannot binary search unsorted collections. If the data arrives in random order and you search it once, linear search is your only option.
• Small collections—for fewer than ~50 elements, the overhead of maintaining a sorted structure or building a hash table exceeds the cost of just scanning. Python’s in operator on lists uses linear search internally.
• Search-once scenarios—if you search a collection exactly once, sorting it first (O(n log n)) and then binary searching (O(log n)) is slower than a single linear scan (O(n)).

Python’s in operator on lists performs a linear search under the hood:

tasks = ["buy groceries", "write tests", "deploy app"]
print("write tests" in tasks)  # True — scans left to right, O(n)

Binary Search

Binary search requires sorted data. It repeatedly cuts the search space in half: compare the target with the middle element, then discard the half that cannot contain the target. This gives O(log n) time—searching one million elements takes at most 20 comparisons.

The algorithm, step by step:

1. Set lo = 0 and hi = len(arr) - 1.
2. While lo <= hi:
   1. Compute mid = (lo + hi) // 2.
   2. If arr[mid] == target, return mid.
   3. If arr[mid] < target, the target is in the right half: set lo = mid + 1.
   4. If arr[mid] > target, the target is in the left half: set hi = mid - 1.
3. If the loop ends without returning, the target is not in the array. Return -1.

def binary_search(arr, target):
    """Return the index of target in sorted arr, or -1 if not found."""
    lo, hi = 0, len(arr) - 1           # 1. Initialize boundaries

    while lo <= hi:                     # 2. Loop while search space is non-empty
        mid = (lo + hi) // 2           #    Find the midpoint
        if arr[mid] == target:         #    2a. Exact match
            return mid
        elif arr[mid] < target:        #    2b. Target is in the right half
            lo = mid + 1               #         Discard left half including mid
        else:                          #    2c. Target is in the left half
            hi = mid - 1              #         Discard right half including mid

    return -1                          # 3. Not found

# Usage
sorted_ids = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(sorted_ids, 23))   # 5
print(binary_search(sorted_ids, 24))   # -1

Binary Search on a Search Space

Binary search is not limited to finding elements in arrays. Any problem where you can answer “is X large enough?” with a yes/no can be solved with binary search on the answer space. This is one of the most powerful algorithmic techniques, and it appears constantly in real engineering.

Problem: You have a list of task durations and a number of workers. Each worker processes tasks sequentially. You want to split the tasks among workers so that the maximum time any single worker spends is minimized. What is that minimum maximum time?

The insight: if you guess a time limit T, you can greedily check whether T is feasible—assign tasks to workers one by one, starting a new worker whenever the current one would exceed T. If you need more than the available workers, T is too small. If you need fewer or exactly enough, T is feasible. The answer is the smallest feasible T.

def min_max_time(durations, num_workers):
    """Find the minimum possible maximum time per worker."""

    def is_feasible(max_time):
        """Can we assign all tasks using <= num_workers if each handles <= max_time?"""
        workers_needed = 1
        current_load = 0
        for d in durations:
            if current_load + d > max_time:
                workers_needed += 1        # Start a new worker
                current_load = d           # This task goes to the new worker
            else:
                current_load += d          # Add task to current worker
        return workers_needed <= num_workers

    lo = max(durations)          # Lower bound: at least the longest single task
    hi = sum(durations)          # Upper bound: one worker does everything

    while lo < hi:
        mid = (lo + hi) // 2
        if is_feasible(mid):
            hi = mid             # mid works — try to find something smaller
        else:
            lo = mid + 1         # mid is too small — need more time

    return lo

# Example: 5 tasks, 3 workers
print(min_max_time([10, 20, 30, 40, 50], 3))  # 60

Notice the slight difference from element-search binary search: here we use lo < hi (not <=) and converge lo and hi to the same value. This is the standard “minimize the maximum” binary search template.

Insertion Sort

Insertion sort builds a sorted portion of the array one element at a time. For each new element, it shifts larger elements rightward to make room, then inserts the element in its correct position.

def insertion_sort(arr):
    """Sort arr in-place using insertion sort."""
    for i in range(1, len(arr)):       # Start from the second element
        key = arr[i]                   # The element to insert
        j = i - 1                      # Start comparing with the element to its left

        # Shift elements that are larger than key one position to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]        # Shift right
            j -= 1                     # Move comparison pointer left

        arr[j + 1] = key               # Insert key in the correct position

    return arr

print(insertion_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]

Complexity: O(n²) worst case (reverse-sorted input), but O(n) best case when data is already nearly sorted. This makes insertion sort excellent for small arrays or arrays that are “almost sorted”—which is surprisingly common in practice. Python’s own Timsort uses insertion sort for small runs.

Merge Sort

Merge sort is a divide-and-conquer algorithm. It recursively splits the array in half until each piece has one element (which is trivially sorted), then merges the sorted halves back together. It guarantees O(n log n) time regardless of input order, and it is stable—equal elements keep their original relative order.

def merge_sort(arr):
    """Return a new sorted list using merge sort."""
    if len(arr) <= 1:                  # Base case: 0 or 1 elements are already sorted
        return arr

    mid = len(arr) // 2                # Find the midpoint
    left = merge_sort(arr[:mid])       # Recursively sort the left half
    right = merge_sort(arr[mid:])      # Recursively sort the right half

    return merge(left, right)          # Merge the two sorted halves

def merge(left, right):
    """Merge two sorted lists into one sorted list."""
    result = []
    i = j = 0                         # Pointers into left and right

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= preserves stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # One of the halves may have remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]

The recursion tree: An 8-element array splits into two 4-element arrays, which split into four 2-element arrays, which split into eight 1-element arrays. That’s log₂ n levels of splitting. At each level, the merge step touches every element once, so each level costs O(n). Total: O(n log n).

Space complexity: O(n)—the merge function creates new lists at each level. This is the trade-off versus in-place sorts like quicksort.

Quicksort

Quicksort is another divide-and-conquer algorithm, but instead of splitting at the midpoint, it partitions the array around a pivot element. All elements smaller than the pivot go to its left; all elements larger go to its right. Then it recursively sorts the left and right partitions.

def quicksort(arr):
    """Return a new sorted list using quicksort."""
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]                # Choose middle element as pivot
    left = [x for x in arr if x < pivot]      # Elements smaller than pivot
    middle = [x for x in arr if x == pivot]    # Elements equal to pivot
    right = [x for x in arr if x > pivot]     # Elements larger than pivot

    return quicksort(left) + middle + quicksort(right)

print(quicksort([10, 7, 8, 9, 1, 5]))  # [1, 5, 7, 8, 9, 10]

This is the “Lomuto-style” list-comprehension version—clear but uses extra space. The in-place Hoare partition scheme is more memory-efficient but harder to read:

def quicksort_inplace(arr, lo=0, hi=None):
    """Sort arr in-place using quicksort with Hoare partition."""
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    # Partition
    pivot = arr[(lo + hi) // 2]
    i, j = lo, hi
    while i <= j:
        while arr[i] < pivot:
            i += 1
        while arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1

    quicksort_inplace(arr, lo, j)
    quicksort_inplace(arr, i, hi)

data = [10, 7, 8, 9, 1, 5]
quicksort_inplace(data)
print(data)  # [1, 5, 7, 8, 9, 10]

Complexity: O(n log n) average case, but O(n²) worst case—this happens when the pivot is always the smallest or largest element (e.g., already-sorted input with first-element pivot). Pivot selection strategies to avoid this:

• Random pivot—pick a random element. Worst case becomes astronomically unlikely.
• Median-of-three—take the median of the first, middle, and last elements. Handles sorted input well.
• Middle element—what we used above. Simple and usually effective.

Heapsort

Heapsort builds a max-heap from the array (as covered in Ch 22), then repeatedly extracts the maximum element and places it at the end. It achieves O(n log n) guaranteed time and is in-place—no extra arrays needed.

def heapsort(arr):
    """Sort arr in-place using heapsort."""
    n = len(arr)

    def sift_down(start, end):
        """Restore the max-heap property from start down to end."""
        root = start
        while 2 * root + 1 <= end:
            child = 2 * root + 1        # Left child
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1              # Right child is larger
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                return

    # Phase 1: Build a max-heap (heapify)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n - 1)

    # Phase 2: Extract max repeatedly
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # Move max to sorted position
        sift_down(0, end - 1)                  # Restore heap on reduced array

    return arr

data = [4, 10, 3, 5, 1]
print(heapsort(data))  # [1, 3, 4, 5, 10]

Heapsort is useful when you need guaranteed O(n log n) with no extra memory. In practice, quicksort is often faster due to better cache locality, but heapsort’s worst case is strictly O(n log n)—no unlucky pivots.

Non-Comparison Sorts

All the sorts above compare pairs of elements. A mathematical result called the comparison lower bound proves that no comparison-based sort can do better than O(n log n). But if your data consists of integers within a known range, you can break this barrier.

Counting sort counts occurrences of each value, then reconstructs the sorted array from the counts. Time: O(n + k) where k is the range of values.

def counting_sort(arr, max_val):
    """Sort non-negative integers using counting sort. O(n + k)."""
    counts = [0] * (max_val + 1)        # One counter per possible value
    for x in arr:
        counts[x] += 1                  # Count occurrences

    result = []
    for val, count in enumerate(counts):
        result.extend([val] * count)    # Emit each value 'count' times
    return result

print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))  # [1, 2, 2, 3, 3, 4, 8]

Radix sort sorts integers digit by digit, from least significant to most significant, using a stable sort (like counting sort) at each digit. Time: O(d × (n + k)) where d is the number of digits and k is the base (usually 10). For fixed-size integers, this is effectively O(n).

Stability

A sort is stable if elements with equal keys maintain their original relative order. This matters when sorting by multiple keys.

Example: you have tasks sorted by creation date. Now you sort by priority. With a stable sort, tasks of the same priority remain in creation-date order. With an unstable sort, their order within a priority level is unpredictable.

Timsort: What Python Actually Uses

When you call sorted() or list.sort() in Python, you get Timsort—a hybrid algorithm invented by Tim Peters in 2002 specifically for Python. Timsort combines merge sort and insertion sort, and it is designed to exploit patterns that appear in real-world data:

• It finds existing sorted “runs” (ascending or descending sequences) in the input.
• Short runs are extended to a minimum length using insertion sort.
• Runs are merged pairwise using a modified merge sort with a “galloping” mode for unbalanced merges.

Timsort is O(n log n) worst case, O(n) on already-sorted data, and stable. It is so effective that Java, Rust, and Swift adopted it for their standard libraries.

The practical takeaway: use Python’s built-in sorted(). It is almost certainly faster than anything you write by hand, because it is implemented in C and uses Timsort’s real-world optimizations. Write your own sort only to learn, or when working in a constrained environment.

Engineering Angle

TaskForge Connection

# TaskForge multi-key sort
tasks = [
    {"title": "Deploy v2", "priority": 1, "due": "2026-03-20", "created": "2026-03-10"},
    {"title": "Write docs", "priority": 2, "due": "2026-03-22", "created": "2026-03-11"},
    {"title": "Fix bug #42", "priority": 1, "due": "2026-03-18", "created": "2026-03-12"},
    {"title": "Code review", "priority": 2, "due": "2026-03-22", "created": "2026-03-09"},
]

# Sort: priority ascending (1=highest), due date ascending, created ascending
sorted_tasks = sorted(tasks, key=lambda t: (t["priority"], t["due"], t["created"]))
for t in sorted_tasks:
    print(f"[P{t['priority']}] {t['due']} - {t['title']}")
# [P1] 2026-03-18 - Fix bug #42
# [P1] 2026-03-20 - Deploy v2
# [P2] 2026-03-22 - Code review   (earlier created date wins)
# [P2] 2026-03-22 - Write docs

Interactive Exercises

Chapter 25 Recursion & Dynamic Programming

Recursive Thinking

A recursive function calls itself with a smaller version of the same problem. Every recursion needs two parts:

1. Base case—a condition that stops the recursion. Without it, the function calls itself forever.
2. Recursive case—the function calls itself with a smaller input that moves toward the base case.

The simplest example is factorial:

def factorial(n):
    """Compute n! = n * (n-1) * ... * 1."""
    if n <= 1:             # Base case: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)  # Recursive case: n! = n * (n-1)!

print(factorial(5))  # 120 = 5 * 4 * 3 * 2 * 1

Walk through the execution:

factorial(5)
  = 5 * factorial(4)
  = 5 * (4 * factorial(3))
  = 5 * (4 * (3 * factorial(2)))
  = 5 * (4 * (3 * (2 * factorial(1))))
  = 5 * (4 * (3 * (2 * 1)))           # Base case reached
  = 5 * (4 * (3 * 2))
  = 5 * (4 * 6)
  = 5 * 24
  = 120

Now Fibonacci—each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

def fib(n):
    """Return the nth Fibonacci number (naive recursive)."""
    if n <= 1:             # Base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)  # Recursive case

print(fib(10))  # 55

This works, but it is catastrophically slow for large n. Why? Because it recomputes the same subproblems over and over. fib(5) calls fib(3) twice, fib(2) three times, and fib(1) five times. The total calls grow exponentially: O(2ⁿ).

The Call Stack

Each recursive call adds a stack frame—a block of memory that stores the function’s local variables and return address. The frames stack up as recursion goes deeper, then unwind as each call returns.

# Visualizing the call stack for factorial(4):
#
# Frame 4: factorial(1) -> returns 1         [TOP]
# Frame 3: factorial(2) -> waiting for frame 4
# Frame 2: factorial(3) -> waiting for frame 3
# Frame 1: factorial(4) -> waiting for frame 2  [BOTTOM]
#
# After factorial(1) returns, frames unwind from top to bottom.

Python imposes a default recursion limit of 1000. You can check and change it:

import sys
print(sys.getrecursionlimit())  # 1000
sys.setrecursionlimit(5000)     # Increase it

Stack Overflow

When recursion goes too deep, you get a RecursionError (Python’s version of a stack overflow). This happens when:

• You forgot the base case
• The base case is wrong and never triggers
• The problem is too large for recursive depth (e.g., processing a linked list of 100,000 elements recursively)

Tail recursion is a pattern where the recursive call is the very last operation in the function. Some languages (Scheme, Scala) optimize this into a loop automatically, eliminating stack growth. Python does not do tail-call optimization. In Python, if you need deep recursion, convert to an explicit loop with a stack data structure.

# Recursive (limited by call stack):
def sum_list_recursive(lst, i=0):
    if i == len(lst):
        return 0
    return lst[i] + sum_list_recursive(lst, i + 1)

# Iterative (no stack limit):
def sum_list_iterative(lst):
    total = 0
    for x in lst:
        total += x
    return total

Memoization

Memoization caches the results of expensive function calls so that if the function is called again with the same arguments, it returns the cached result instead of recomputing. This transforms our O(2ⁿ) Fibonacci into O(n).

def fib_memo(n, cache={}):
    """Fibonacci with manual memoization."""
    if n in cache:             # Already computed? Return cached result.
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_memo(50))  # 12586269025 — instant, not heat-death-of-the-universe

Python provides a built-in decorator that does this automatically:

from functools import lru_cache

@lru_cache(maxsize=None)    # Cache all results (no eviction)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)

print(fib_cached(100))  # 354224848179261915075

The difference is dramatic. Let’s time it:

import time

# Naive recursive — try n=35 (anything higher may freeze your machine)
start = time.time()
fib(35)
print(f"Naive: {time.time() - start:.2f}s")  # ~3-5 seconds

# Memoized — same n but now try n=500
start = time.time()
fib_cached(500)
print(f"Memoized: {time.time() - start:.6f}s")  # ~0.000 seconds

Bottom-Up Tabulation

Memoization is “top-down”—you start from the big problem and recurse down. Tabulation is “bottom-up”—you build a table starting from the base cases and work upward. No recursion, no stack overhead.

def fib_table(n):
    """Fibonacci using bottom-up tabulation."""
    if n <= 1:
        return n

    table = [0] * (n + 1)     # table[i] will hold fib(i)
    table[0] = 0               # Base case
    table[1] = 1               # Base case

    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]   # Build from smaller subproblems

    return table[n]

print(fib_table(100))  # 354224848179261915075

You can even optimize space to O(1) since you only need the previous two values:

def fib_optimal(n):
    """Fibonacci with O(1) space."""
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

print(fib_optimal(100))  # 354224848179261915075

Classic DP Patterns

Coin Change: Minimum Coins to Make a Target Amount

Problem: Given coin denominations (e.g., [1, 5, 10, 25]) and a target amount, find the minimum number of coins needed.

This is the canonical DP problem. The key insight: the minimum coins for amount a is 1 + the minimum over all coins c of the answer for amount a - c.

def coin_change(coins, amount):
    """Return minimum coins to make amount, or -1 if impossible."""
    # dp[i] = minimum coins needed to make amount i
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0                          # Base case: 0 coins for amount 0

    for a in range(1, amount + 1):     # For each amount from 1 to target
        for c in coins:                # Try each coin denomination
            if c <= a:                 # Coin must not exceed the current amount
                dp[a] = min(dp[a], dp[a - c] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 10, 25], 36))  # 3 (25 + 10 + 1)
print(coin_change([3, 7], 5))            # -1 (impossible)

Complexity: O(amount × len(coins)). Each cell in the table is computed once, using a constant amount of work per coin.

Longest Common Subsequence (LCS)

Problem: Given two strings, find the length of their longest common subsequence—the longest sequence of characters that appears in both strings in the same order (but not necessarily contiguously).

This is the foundation of diff algorithms (like git diff): they find the LCS of two files, and everything not in the LCS is a change.

def lcs(s1, s2):
    """Return the length of the longest common subsequence."""
    m, n = len(s1), len(s2)
    # dp[i][j] = LCS length of s1[:i] and s2[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:          # Characters match
                dp[i][j] = dp[i - 1][j - 1] + 1  # Extend the LCS
            else:                                  # Characters differ
                dp[i][j] = max(dp[i - 1][j],      # Skip char from s1
                               dp[i][j - 1])      # Skip char from s2

    return dp[m][n]

print(lcs("ABCBDAB", "BDCAB"))  # 4 ("BCAB")

0/1 Knapsack: Maximize Value Within a Weight Limit

Problem: You have items with weights and values. You have a knapsack with a weight capacity. Maximize the total value without exceeding the capacity. Each item can be taken at most once.

def knapsack(values, weights, capacity):
    """Return maximum value achievable within capacity."""
    n = len(values)
    # dp[i][w] = max value using items 0..i-1 with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # Don't take item i
            if weights[i - 1] <= w:                 # Can we take item i?
                take = dp[i - 1][w - weights[i - 1]] + values[i - 1]
                dp[i][w] = max(dp[i][w], take)     # Take it if better

    return dp[n][capacity]

# Items: (value, weight)
values  = [60, 100, 120]
weights = [10,  20,  30]
capacity = 50
print(knapsack(values, weights, capacity))  # 220 (items 2 and 3)

Complexity: O(n × capacity). This is called pseudo-polynomial—it depends on the numeric value of capacity, not just the input size.

Recognizing DP Problems

Not every problem benefits from DP. Two properties must hold:

1. Overlapping subproblems—the same subproblem is solved multiple times. If every subproblem is unique (like merge sort), DP adds overhead without benefit.
2. Optimal substructure—the optimal solution to the whole problem can be built from optimal solutions to subproblems. If changing a sub-decision doesn’t affect other sub-decisions, the problem has optimal substructure.

Quick test: Can you write a recursive solution? Does it recompute the same subproblems? If yes to both, add memoization. If you can identify the subproblem table dimensions, write the bottom-up version.

Engineering Angle

TaskForge Connection

def select_tasks(tasks, time_budget):
    """Select tasks to maximize total value within time_budget.
    Each task is a dict with 'title', 'time', and 'value' keys.
    Returns list of selected task titles.
    """
    n = len(tasks)
    dp = [[0] * (time_budget + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        t = tasks[i - 1]
        for w in range(time_budget + 1):
            dp[i][w] = dp[i - 1][w]              # Don't take this task
            if t["time"] <= w:
                take = dp[i - 1][w - t["time"]] + t["value"]
                dp[i][w] = max(dp[i][w], take)

    # Backtrack to find which tasks were selected
    selected = []
    w = time_budget
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected.append(tasks[i - 1]["title"])
            w -= tasks[i - 1]["time"]

    return selected

sprint_tasks = [
    {"title": "Auth system",     "time": 8,  "value": 90},
    {"title": "Search feature",  "time": 5,  "value": 60},
    {"title": "Fix CSS bug",     "time": 1,  "value": 20},
    {"title": "API pagination",  "time": 3,  "value": 45},
    {"title": "Dark mode",       "time": 4,  "value": 30},
]
print(select_tasks(sprint_tasks, 10))
# ['API pagination', 'Search feature', 'Fix CSS bug'] — value 125 in 9 hours

Interactive Exercises

Chapter 26 Algorithm Patterns

Two Pointers

The two-pointer technique uses two indices that move through an array, either toward each other from opposite ends or in the same direction at different speeds. It turns many O(n²) brute-force solutions into O(n).

Pattern 1: Converging Pointers (Opposite Ends)

Problem: Given a sorted array and a target sum, find a pair of elements that adds up to the target.

def two_sum_sorted(arr, target):
    """Find two numbers in sorted arr that sum to target. Return their indices."""
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1          # Need a bigger sum — move left pointer right
        else:
            right -= 1         # Need a smaller sum — move right pointer left

    return None                # No pair found

print(two_sum_sorted([1, 3, 5, 7, 11, 15], 16))  # (2, 4) — 5 + 11

Why it works: Since the array is sorted, moving the left pointer right increases the sum, and moving the right pointer left decreases it. We never need to check pairs we’ve already ruled out.

Pattern 2: Palindrome Check

def is_palindrome(s):
    """Check if string is a palindrome, ignoring case and non-alphanumeric chars."""
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1

    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True

Pattern 3: Remove Duplicates In-Place

def remove_duplicates(arr):
    """Remove duplicates from sorted arr in-place. Return new length."""
    if not arr:
        return 0

    write = 1                          # Position to write next unique element
    for read in range(1, len(arr)):    # Scan through the array
        if arr[read] != arr[read - 1]: # Found a new value
            arr[write] = arr[read]     # Write it
            write += 1

    return write

data = [1, 1, 2, 2, 2, 3, 4, 4, 5]
new_len = remove_duplicates(data)
print(data[:new_len])  # [1, 2, 3, 4, 5]

Sliding Window

The sliding window technique maintains a “window” (a contiguous subarray or substring) and slides it across the data. There are two types:

Fixed-Size Window: Maximum Sum of k Consecutive Elements

def max_sum_k(arr, k):
    """Return the maximum sum of k consecutive elements."""
    if len(arr) < k:
        return None

    # Compute the sum of the first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide: add the next element, remove the leftmost element
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # Slide the window
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_k([2, 1, 5, 1, 3, 2], 3))  # 9 (5 + 1 + 3)

Instead of recomputing the sum of k elements at each position (O(n × k)), we adjust by one element (O(1)), giving O(n) total.

Variable-Size Window: Longest Substring Without Repeating Characters

def longest_unique_substring(s):
    """Return the length of the longest substring without repeating characters."""
    seen = {}                  # Map character -> its most recent index
    max_len = 0
    start = 0                  # Left edge of the window

    for end in range(len(s)):  # Right edge expands
        if s[end] in seen and seen[s[end]] >= start:
            start = seen[s[end]] + 1   # Shrink: jump past the duplicate
        seen[s[end]] = end
        max_len = max(max_len, end - start + 1)

    return max_len

print(longest_unique_substring("abcabcbb"))  # 3 ("abc")
print(longest_unique_substring("pwwkew"))    # 3 ("wke")

Variable-Size Window: Smallest Subarray with Sum ≥ Target

def min_subarray_sum(arr, target):
    """Return the length of the smallest subarray with sum >= target, or 0."""
    min_len = float('inf')
    window_sum = 0
    start = 0

    for end in range(len(arr)):
        window_sum += arr[end]             # Expand window

        while window_sum >= target:        # Shrink while condition holds
            min_len = min(min_len, end - start + 1)
            window_sum -= arr[start]
            start += 1

    return min_len if min_len != float('inf') else 0

print(min_subarray_sum([2, 3, 1, 2, 4, 3], 7))  # 2 ([4, 3])

Greedy

A greedy algorithm makes the locally optimal choice at each step, hoping to find the global optimum. Greedy works when the problem has the greedy choice property—a locally optimal choice leads to a globally optimal solution.

When Greedy Works: Interval Scheduling

Problem: Given a set of intervals (start, end), find the maximum number of non-overlapping intervals.

Strategy: Always pick the interval that ends earliest. This leaves the most room for future intervals.

def max_non_overlapping(intervals):
    """Return max number of non-overlapping intervals.
    Each interval is (start, end).
    """
    # Sort by end time
    intervals.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:      # No overlap with previous selection
            count += 1
            last_end = end         # Update the end boundary

    return count

meetings = [(1, 3), (2, 5), (3, 6), (5, 7), (8, 10), (6, 9)]
print(max_non_overlapping(meetings))  # 3: (1,3), (5,7), (8,10)

When Greedy Fails: Coin Change with Weird Denominations

Greedy works for US coin denominations (25, 10, 5, 1): always pick the largest coin that fits. But consider denominations [1, 3, 4] and amount 6:

• Greedy: 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

The greedy approach picks the biggest coin first, but that blocks the better solution. This is why we needed DP for the general coin change problem in Ch 25.

Divide and Conquer

Divide and conquer splits a problem into independent subproblems, solves each recursively, and combines the results. You already know merge sort (Ch 24). The pattern applies beyond sorting:

• Closest pair of points—split the points by x-coordinate, find closest pair in each half, then check across the divide.
• Counting inversions—a modified merge sort that counts how many pairs are out of order.
• Karatsuba multiplication—multiply large numbers by splitting them into halves, reducing from O(n²) to O(n¹·⁵⁸).

The key distinction from DP: divide and conquer subproblems are independent (no overlapping). DP subproblems overlap.

Backtracking

Backtracking explores all possible choices, but prunes branches that cannot lead to a valid solution. It is a systematic way to try everything without wasting time on dead ends.

The pattern: make a choice, recurse, undo the choice (backtrack), try the next option.

Example: Generate All Subsets

def subsets(nums):
    """Generate all subsets of nums."""
    result = []

    def backtrack(start, current):
        result.append(current[:])          # Add a copy of the current subset

        for i in range(start, len(nums)):
            current.append(nums[i])        # Choose
            backtrack(i + 1, current)      # Explore
            current.pop()                  # Un-choose (backtrack)

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Example: N-Queens (Determine if n queens can be placed on an n×n board)

def solve_n_queens(n):
    """Return the number of ways to place n queens on an n x n board
    so that no two queens attack each other."""
    solutions = 0
    cols = set()          # Columns with queens
    diag1 = set()         # "row - col" diagonals with queens
    diag2 = set()         # "row + col" diagonals with queens

    def backtrack(row):
        nonlocal solutions
        if row == n:               # All queens placed successfully
            solutions += 1
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue           # Prune: this position is attacked

            # Place queen
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)

            backtrack(row + 1)     # Try next row

            # Remove queen (backtrack)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

print(solve_n_queens(8))  # 92 solutions

Pattern Decision Framework

When you encounter a problem, use this decision framework to identify which pattern applies:

Engineering Angle

TaskForge Connection

def max_completions_in_window(completion_days, window_size=7):
    """Return the maximum number of tasks completed in any window_size-day period.
    completion_days is a sorted list of day numbers when tasks were completed.
    """
    if not completion_days:
        return 0

    max_count = 0
    start = 0

    for end in range(len(completion_days)):
        # Shrink window: remove tasks outside the window
        while completion_days[end] - completion_days[start] >= window_size:
            start += 1
        # All tasks from start to end are within the window
        max_count = max(max_count, end - start + 1)

    return max_count

# Task completions on these days:
days = [1, 2, 3, 5, 8, 9, 10, 11, 15, 16]
print(max_completions_in_window(days, 7))  # 5 (days 5,8,9,10,11)

Interactive Exercises

Chapter 27 Graph Algorithms & Problem Solving

BFS (Breadth-First Search)

Breadth-first search explores a graph level by level, visiting all neighbors of the current node before moving to the next level. It uses a queue (FIFO)—the data structure from Ch 20. BFS finds the shortest path in unweighted graphs because it discovers nodes in order of their distance from the start.

from collections import deque

def bfs(graph, start):
    """Perform BFS from start node. Return dict of {node: distance}.
    graph: dict of {node: [neighbors]}
    """
    visited = {start: 0}              # node -> distance from start
    queue = deque([start])

    while queue:
        node = queue.popleft()         # Dequeue the front node
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited[neighbor] = visited[node] + 1
                queue.append(neighbor) # Enqueue unvisited neighbor

    return visited

# Example graph:
#   A -- B -- D
#   |         |
#   C -- E -- F
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B', 'F'],
    'E': ['C', 'F'],
    'F': ['D', 'E'],
}
distances = bfs(graph, 'A')
print(distances)
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

Complexity: O(V + E) where V is vertices and E is edges. Each node is visited once, and each edge is examined once.

BFS Shortest Path (Reconstructing the Path)

from collections import deque

def bfs_path(graph, start, end):
    """Return the shortest path from start to end, or None."""
    if start == end:
        return [start]

    visited = {start}
    queue = deque([(start, [start])])  # (node, path_so_far)

    while queue:
        node, path = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # No path exists

print(bfs_path(graph, 'A', 'F'))  # ['A', 'B', 'D', 'F'] or ['A', 'C', 'E', 'F']

DFS (Depth-First Search)

Depth-first search explores as deep as possible along each branch before backtracking. It uses a stack (LIFO)—either the call stack (via recursion) or an explicit stack data structure.

Recursive DFS

def dfs_recursive(graph, node, visited=None):
    """Perform DFS from node. Return list of visited nodes in order."""
    if visited is None:
        visited = []
    visited.append(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'F', 'E', 'C']

Iterative DFS

def dfs_iterative(graph, start):
    """Perform DFS from start using an explicit stack."""
    visited = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            # Add neighbors in reverse to visit them in order
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited

print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'F', 'E', 'C']

DFS applications:

• Cycle detection—during DFS on a directed graph, if you encounter a node currently in the recursion stack (not just visited), there is a cycle.
• Topological sort—covered below.
• Connected components—run DFS from each unvisited node; each DFS discovers one component.
• Path finding—DFS finds a path but not necessarily the shortest.

Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path in a weighted graph with non-negative weights. It uses a priority queue (min-heap from Ch 22) to always process the closest unvisited node first.

Walk through the algorithm:

1. Set the distance to the start node to 0, and all other distances to infinity.
2. Add the start node to a priority queue with distance 0.
3. While the priority queue is not empty:
   1. Extract the node with the smallest distance.
   2. For each neighbor, calculate the distance through the current node.
   3. If this distance is shorter than the neighbor’s current distance, update it and add the neighbor to the queue.

import heapq

def dijkstra(graph, start):
    """Find shortest distances from start to all nodes.
    graph: dict of {node: [(neighbor, weight), ...]}
    Returns: dict of {node: shortest_distance}
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]             # (distance, node)
    visited = set()

    while pq:
        dist, node = heapq.heappop(pq)

        if node in visited:        # Already processed with a shorter distance
            continue
        visited.add(node)

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return distances

# Weighted graph:
#   A --4-- B --2-- D
#   |       |       |
#   1       3       1
#   |       |       |
#   C --5-- E --1-- F
weighted = {
    'A': [('B', 4), ('C', 1)],
    'B': [('A', 4), ('D', 2), ('E', 3)],
    'C': [('A', 1), ('E', 5)],
    'D': [('B', 2), ('F', 1)],
    'E': [('B', 3), ('C', 5), ('F', 1)],
    'F': [('D', 1), ('E', 1)],
}
print(dijkstra(weighted, 'A'))
# {'A': 0, 'B': 4, 'C': 1, 'D': 6, 'E': 6, 'F': 7}

Complexity: O((V + E) log V) with a binary heap. The log V factor comes from heap operations.

Reconstructing the Shortest Path

import heapq

def dijkstra_path(graph, start, end):
    """Find the shortest path and its distance from start to end."""
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    previous = {node: None for node in graph}  # Track the path
    pq = [(0, start)]
    visited = set()

    while pq:
        dist, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)

        if node == end:
            break

        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                previous[neighbor] = node
                heapq.heappush(pq, (new_dist, neighbor))

    # Reconstruct path
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = previous[current]
    path.reverse()

    return path, distances[end]

path, dist = dijkstra_path(weighted, 'A', 'F')
print(f"Path: {path}, Distance: {dist}")
# Path: ['A', 'B', 'D', 'F'], Distance: 7

Topological Sort

Topological sort produces a linear ordering of nodes in a directed acyclic graph (DAG) such that for every edge u → v, u appears before v. This is the algorithm that resolves dependencies: build systems, package managers, course prerequisites, and task scheduling.

Kahn’s Algorithm (BFS-Based)

Kahn’s algorithm uses in-degree tracking: start with nodes that have no incoming edges (in-degree 0), process them, reduce the in-degree of their neighbors, and repeat.

from collections import deque

def topological_sort_kahn(graph):
    """Return a topological ordering of the DAG, or None if a cycle exists.
    graph: dict of {node: [dependents]} (edges point from dependency to dependent)
    """
    # Step 1: Compute in-degrees
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

    # Step 2: Start with all nodes that have in-degree 0
    queue = deque([node for node in graph if in_degree[node] == 0])
    result = []

    # Step 3: Process nodes
    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1       # One dependency satisfied
            if in_degree[neighbor] == 0:   # All dependencies satisfied
                queue.append(neighbor)

    # Step 4: Check for cycles
    if len(result) != len(graph):
        return None  # Cycle detected! Not all nodes were processed.

    return result

# TaskForge dependency DAG:
#   "setup" -> "backend" -> "deploy"
#   "setup" -> "frontend" -> "deploy"
#   "backend" -> "tests"
deps = {
    "setup":    ["backend", "frontend"],
    "backend":  ["tests", "deploy"],
    "frontend": ["deploy"],
    "tests":    [],
    "deploy":   [],
}
print(topological_sort_kahn(deps))
# ['setup', 'backend', 'frontend', 'tests', 'deploy']

DFS-Based Topological Sort

def topological_sort_dfs(graph):
    """Topological sort using DFS (post-order reverse)."""
    visited = set()
    stack = []         # Will contain the reverse post-order
    in_progress = set()  # For cycle detection

    def dfs(node):
        if node in in_progress:
            return False           # Cycle detected
        if node in visited:
            return True

        in_progress.add(node)
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        in_progress.remove(node)
        visited.add(node)
        stack.append(node)         # Post-order: add after all descendants
        return True

    for node in graph:
        if node not in visited:
            if not dfs(node):
                return None        # Cycle

    stack.reverse()                # Reverse post-order = topological order
    return stack

print(topological_sort_dfs(deps))
# ['setup', 'frontend', 'backend', 'tests', 'deploy']

Complexity: Both algorithms run in O(V + E).

Union-Find (Disjoint Set)

Union-Find tracks connected components efficiently. It supports two operations:

• find(x)—returns the root representative of x’s component.
• union(x, y)—merges the components containing x and y.

With path compression (flatten the tree during find) and union by rank (attach the smaller tree under the larger), both operations run in near-constant time: O(α(n)) amortized, where α is the inverse Ackermann function—effectively O(1) for all practical purposes.

class UnionFind:
    """Disjoint Set with path compression and union by rank."""

    def __init__(self, n):
        self.parent = list(range(n))   # Each node is its own parent initially
        self.rank = [0] * n            # Rank (approximate tree height)
        self.components = n            # Number of distinct components

    def find(self, x):
        """Return the root of x's component (with path compression)."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Flatten the tree
        return self.parent[x]

    def union(self, x, y):
        """Merge the components of x and y. Return True if they were separate."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False               # Already in the same component

        # Attach smaller tree under larger tree
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

        self.components -= 1
        return True

    def connected(self, x, y):
        """Check if x and y are in the same component."""
        return self.find(x) == self.find(y)

# Example: network of 6 servers
uf = UnionFind(6)
uf.union(0, 1)   # Connect server 0 and 1
uf.union(2, 3)   # Connect server 2 and 3
uf.union(1, 3)   # Connect the two clusters

print(uf.connected(0, 3))  # True — all four are connected
print(uf.connected(0, 4))  # False — server 4 is isolated
print(uf.components)        # 3 (cluster {0,1,2,3}, isolated 4, isolated 5)

Use cases: detecting whether adding an edge creates a cycle (Kruskal’s MST algorithm), checking network connectivity, grouping related items (e.g., duplicate photo detection).

Problem-Solving Framework

When you encounter a graph problem, use this systematic approach:

1. Understand the problem—what are the nodes? What are the edges? Are they directed? Weighted? What are you looking for?
2. Identify the shape:
   • Shortest path in unweighted graph → BFS
   • Shortest path in weighted graph (non-negative) → Dijkstra
   • Dependency ordering → Topological sort
   • Component connectivity → Union-Find or BFS/DFS
   • Cycle detection (directed) → DFS with in-progress tracking
   • Cycle detection (undirected) → Union-Find
   • All paths / explore all possibilities → DFS + backtracking
3. Implement and verify—test with edge cases: empty graph, single node, disconnected components, cycles.

Engineering Angle

TaskForge Connection

from collections import deque

def resolve_task_order(tasks):
    """Given a dict of {task: [dependencies]}, return a valid execution order.
    Raises ValueError if there is a circular dependency.
    """
    # Build the forward graph and compute in-degrees
    graph = {t: [] for t in tasks}
    in_degree = {t: 0 for t in tasks}

    for task, deps in tasks.items():
        for dep in deps:
            graph[dep].append(task)    # dep must come before task
            in_degree[task] += 1

    # Kahn's algorithm
    queue = deque([t for t in tasks if in_degree[t] == 0])
    order = []

    while queue:
        task = queue.popleft()
        order.append(task)
        for dependent in graph[task]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                queue.append(dependent)

    if len(order) != len(tasks):
        raise ValueError("Circular dependency detected! Cannot determine order.")

    return order

# TaskForge sprint tasks with dependencies
sprint = {
    "Set up database":    [],
    "Build API":          ["Set up database"],
    "Build frontend":     ["Build API"],
    "Write tests":        ["Build API"],
    "Deploy":             ["Build frontend", "Write tests"],
}

print(resolve_task_order(sprint))
# ['Set up database', 'Build API', 'Build frontend', 'Write tests', 'Deploy']

# Detect circular dependency
try:
    circular = {
        "A": ["B"],
        "B": ["C"],
        "C": ["A"],  # Cycle!
    }
    resolve_task_order(circular)
except ValueError as e:
    print(e)  # "Circular dependency detected! Cannot determine order."

Interactive Exercises

Phase Gate 6 Algorithms Checkpoint

What You Can Do Now

TaskForge Checkpoint