Python Algorithm Cookbook

Common Algorithm Patterns

Sliding Window (Two Pointers)

# Pattern: Longest Substring Without Repeating Characters
def length_of_longest_substring(s: str) -> int:
    """Find length of longest substring without repeating characters.

    Sliding window technique with hash map to track character positions.
    Time: O(n), Space: O(min(n, alphabet_size))

    Example: "abcabcbb" -> 3 (substring "abc")
    """
    if not s:
        return 0

    # Track last seen index of each character
    char_index: dict[str, int] = {}
    max_length = 0
    left = 0  # Left pointer of sliding window

    for right, char in enumerate(s):
        # If character seen AND it's within current window
        if char in char_index and char_index[char] >= left:
            # Move left pointer past the previous occurrence
            # This maintains "no repeating chars" invariant
            left = char_index[char] + 1

        # Update character's latest position
        char_index[char] = right

        # Update max length seen so far
        # Current window size is (right - left + 1)
        max_length = max(max_length, right - left + 1)

    return max_length

# Sliding Window Key Principles:
# 1. Two pointers: left (start) and right (end) define window
# 2. Expand window by incrementing right pointer
# 3. Contract window by incrementing left when constraint violated
# 4. Track window state with hash map, set, or counter
# 5. Update result during expansion or contraction
# Common uses: substring/subarray with constraints (unique chars, max sum, min length)

BFS Tree Traversal (Level Order)

# Pattern: Binary Tree Level Order Traversal (BFS)
from collections import deque
from typing import Optional

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

def level_order_traversal(root: Optional[TreeNode]) -> list[list[int]]:
    """Perform BFS level-order traversal of binary tree.

    Returns list of lists where each inner list contains node values at that level.
    Time: O(n), Space: O(w) where w is max width of tree

    Example:
        Input:     3
                  / \
                 9  20
                   /  \
                  15   7
        Output: [[3], [9, 20], [15, 7]]
    """
    if not root:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        # CRITICAL: Capture level size BEFORE processing
        # This separates current level from next level nodes
        level_size = len(queue)
        current_level: list[int] = []

        # Process exactly level_size nodes (all nodes at current level)
        for _ in range(level_size):
            node = queue.popleft()  # O(1) with deque
            current_level.append(node.val)

            # Add children for next level processing
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

# BFS Key Principles:
# 1. Use collections.deque for O(1) append/popleft operations (NOT list)
# 2. Capture level_size = len(queue) before inner loop to separate levels
# 3. Process entire level before moving to next (prevents mixing levels)
# 4. Add children during current level processing
# Common uses: level order traversal, shortest path, connected components, graph exploration

Binary Search on Two Arrays

# Pattern: Median of two sorted arrays
def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    """Find median of two sorted arrays in O(log(min(m,n))) time.

    Strategy: Binary search on smaller array to find partition point
    """
    # Ensure nums1 is smaller for optimization
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    left, right = 0, m

    while left <= right:
        partition1 = (left + right) // 2
        partition2 = (m + n + 1) // 2 - partition1

        # Handle edge cases with infinity
        max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        min_right1 = float('inf') if partition1 == m else nums1[partition1]

        max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        min_right2 = float('inf') if partition2 == n else nums2[partition2]

        # Check if partition is valid
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            # Found correct partition
            if (m + n) % 2 == 0:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
            return max(max_left1, max_left2)
        elif max_left1 > min_right2:
            right = partition1 - 1
        else:
            left = partition1 + 1

    raise ValueError("Input arrays must be sorted")

Hash Map for O(1) Lookup

# Pattern: Two sum problem
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Find indices of two numbers that sum to target.

    Time: O(n), Space: O(n)
    """
    seen: dict[int, int] = {}

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i

    return None

When to Use Each Pattern

• Sliding Window: Substring/subarray with constraints (unique chars, max/min sum, fixed/variable length)
• BFS with Deque: Tree/graph level-order traversal, shortest path, connected components
• Binary Search on Two Arrays: Median, kth element in sorted arrays (O(log n))
• Hash Map: O(1) lookups to convert O(n^2) nested loops to O(n) single pass