Python Patterns Primer — Canonical Solutions for Coding Interviews

def max_sum_subarray(nums: list[int], k: int) -> int:
    """Maximum sum of any contiguous subarray of size k."""
    window_sum = sum(nums[:k])      # seed the first window once — O(k)
    best = window_sum
    # Slide: each step ADD the incoming element and REMOVE the outgoing one.
    # This is why it's O(n) not O(n*k): we never re-sum the whole window.
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]  # +incoming  -outgoing
        best = max(best, window_sum)
    return best

def longest_substring_k_distinct(s: str, k: int) -> int:
    """Longest substring with at most k distinct characters."""
    from collections import defaultdict
    counts = defaultdict(int)   # char -> how many times it's in the current window
    left = 0
    best = 0

    for right, ch in enumerate(s):
        counts[ch] += 1         # the new right-edge char enters the window

        # WHY a while, not an if: adding one char can push us over the limit,
        # and we must shrink until valid again. In some problems one shrink step
        # suffices, but `while` is the safe general form.
        while len(counts) > k:
            left_ch = s[left]
            counts[left_ch] -= 1
            if counts[left_ch] == 0:
                del counts[left_ch]   # remove so len(counts) = true distinct count
            left += 1                 # shrink the window from the left

        # At this point [left..right] is the largest valid window ending at `right`.
        best = max(best, right - left + 1)

    return best

def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
    """Return indices of two numbers in a SORTED array that sum to target."""
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1     # sum too small -> need a bigger number -> move left up
        else:
            right -= 1    # sum too big   -> need a smaller number -> move right down
    return None

def remove_duplicates(nums: list[int]) -> int:
    """In-place dedup of a sorted array. Returns new length. O(1) extra space."""
    if not nums:
        return 0
    slow = 0   # slow marks the last position of the deduped prefix
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:   # found a new unique value
            slow += 1
            nums[slow] = nums[fast]    # write it just after the deduped prefix
    return slow + 1

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:        # fast moves 2, so check fast AND fast.next exist
        slow = slow.next             # 1 step
        fast = fast.next.next        # 2 steps
        if slow is fast:             # they collided -> there is a cycle
            return True
    return False                     # fast hit the end -> no cycle

def find_middle(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    # When fast reaches the end, slow has covered exactly half the distance.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def binary_search(nums: list[int], target: int) -> int:
    """Return index of target, or -1 if absent."""
    lo, hi = 0, len(nums) - 1        # INCLUSIVE bounds: [lo, hi]
    while lo <= hi:                  # <= because the bounds are inclusive; when
                                     # lo == hi there is still one element to check
        mid = lo + (hi - lo) // 2    # avoids integer overflow in other languages;
                                     # harmless habit in Python
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1             # target is to the RIGHT; discard mid and left
        else:
            hi = mid - 1             # target is to the LEFT; discard mid and right
    return -1

def lower_bound(nums: list[int], target: int) -> int:
    """First index i where nums[i] >= target (== len(nums) if none)."""
    lo, hi = 0, len(nums)            # EXCLUSIVE upper bound: [lo, hi)
    while lo < hi:                   # < because hi is exclusive
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1             # mid is too small -> answer is strictly right
        else:
            hi = mid                 # mid might BE the answer -> keep it in range
    return lo                        # lo == hi == the boundary

def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    """Count contiguous subarrays whose sum is exactly k."""
    from collections import defaultdict
    # seen[prefix] = number of times that running prefix sum has occurred.
    # Seed with {0: 1} to count subarrays that start at index 0
    # (a prefix of exactly k means the whole prefix IS a valid subarray).
    seen = defaultdict(int)
    seen[0] = 1

    running = 0
    count = 0
    for x in nums:
        running += x
        # If some earlier prefix equalled (running - k), then the subarray
        # BETWEEN that point and here sums to exactly k. WHY: running - earlier = k.
        count += seen[running - k]
        seen[running] += 1   # record current prefix for future queries
    return count

def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Two Sum on an UNSORTED array, single pass, O(n)."""
    seen = {}   # value -> index where we saw it
    for i, num in enumerate(nums):
        complement = target - num
        # WHY check before inserting: prevents using the same element twice,
        # and guarantees the matched index is strictly earlier.
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words that are anagrams of each other."""
    from collections import defaultdict
    groups = defaultdict(list)
    for w in words:
        # WHY sorted(w): two words are anagrams IFF their sorted letters match,
        # so the sorted tuple is a canonical key shared by all anagrams.
        key = tuple(sorted(w))
        groups[key].append(w)
    return list(groups.values())

def daily_temperatures(temps: list[int]) -> list[int]:
    """For each day, how many days until a warmer temperature (0 if none)."""
    result = [0] * len(temps)
    stack = []   # holds INDICES of days awaiting a warmer day; temps at these
                 # indices are in decreasing order from bottom to top.

    for i, t in enumerate(temps):
        # Today is warmer than the days on top of the stack -> resolve them.
        while stack and temps[stack[-1]] < t:
            prev_day = stack.pop()
            result[prev_day] = i - prev_day   # distance to the warmer day
        stack.append(i)   # today now waits for ITS warmer day
    # Anything left on the stack never found a warmer day -> stays 0.
    return result

from collections import deque

def bfs_shortest_path(grid: list[list[int]], start: tuple, goal: tuple) -> int:
    """Fewest steps from start to goal in a grid. 0 = open, 1 = wall. -1 if unreachable."""
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, 0)])      # (cell, distance-so-far)
    visited = {start}                # mark on ENQUEUE, not dequeue — WHY: prevents
                                     # the same cell being queued multiple times.

    while queue:
        (r, c), dist = queue.popleft()   # popleft = FIFO = level order
        if (r, c) == goal:
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):  # 4-directional neighbours
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1

def count_islands(grid: list[list[str]]) -> int:
    """Count connected groups of '1's (land) in a grid. Classic DFS flood-fill."""
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        # Out of bounds or water -> stop. This is the recursion base case.
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
            return
        grid[r][c] = '0'   # mark visited IN PLACE by sinking the land -> no
                           # separate visited set needed, and avoids revisiting.
        sink(r + 1, c); sink(r - 1, c)   # explore all 4 neighbours deeply
        sink(r, c + 1); sink(r, c - 1)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':   # found an unvisited piece of land
                islands += 1        # it's a new island...
                sink(r, c)          # ...flood-fill the entire island so we don't recount it
    return islands

import heapq

def top_k_largest(nums: list[int], k: int) -> list[int]:
    """Return the k largest numbers."""
    # Python's heapq is a MIN-heap. To keep the k LARGEST, we keep a min-heap of
    # size k: the smallest of our current top-k sits at the root, ready to be
    # evicted the moment we find something bigger.
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)   # drop the smallest -> heap retains the k largest
    return heap   # the k largest, in no particular order

def k_most_frequent(nums: list[int], k: int) -> list[int]:
    """K most frequent elements."""
    from collections import Counter
    counts = Counter(nums)
    # heapq.nlargest with a key is the idiomatic one-liner for top-k by a metric.
    return heapq.nlargest(k, counts.keys(), key=counts.get)

def subsets(nums: list[int]) -> list[list[int]]:
    """Generate all subsets (the power set)."""
    result = []
    path = []   # the subset we're currently building

    def backtrack(start: int):
        # Every node in the recursion tree is itself a valid subset, so we record
        # a COPY of path at every entry (copy because path keeps mutating).
        result.append(path[:])

        # `start` prevents revisiting earlier elements -> avoids duplicate subsets
        # like [1,2] and [2,1] (subsets are unordered).
        for i in range(start, len(nums)):
            path.append(nums[i])      # CHOOSE element i
            backtrack(i + 1)          # EXPLORE further choices after i
            path.pop()                # UN-CHOOSE (backtrack) so the next i starts clean

    backtrack(0)
    return result

def climb_stairs(n: int) -> int:
    """Number of distinct ways to climb n stairs taking 1 or 2 steps at a time."""
    # WHY this recurrence: to reach step n, your last move was either a 1-step
    # (from n-1) or a 2-step (from n-2). So ways(n) = ways(n-1) + ways(n-2).
    if n <= 2:
        return n
    # We only ever need the previous TWO values, so we keep two variables
    # instead of a full array -> O(1) space.
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

def unique_paths(m: int, n: int) -> int:
    """Number of paths from top-left to bottom-right moving only right or down."""
    # dp[j] = number of ways to reach the current cell in column j.
    # WHY a 1-D array works for a 2-D problem: when we process row by row,
    # dp[j] (before update) holds the cell ABOVE, and dp[j-1] holds the cell
    # to the LEFT — exactly the two predecessors of the current cell.
    dp = [1] * n   # first row: only one way to reach each cell (keep going right)
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]   # ways from above (old dp[j]) + ways from left (dp[j-1])
    return dp[-1]

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """Merge all overlapping intervals."""
    if not intervals:
        return []
    # Sort by start. WHY: after sorting, if interval B overlaps anything, it
    # overlaps the interval immediately before it in the sorted list.
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            # Overlap: extend the last interval's end if this one reaches further.
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])   # disjoint -> start a new interval
    return merged

def reverse_list(head: ListNode | None) -> ListNode | None:
    """Reverse a singly linked list in place. O(n) time, O(1) space."""
    prev = None        # the reversed portion built so far (starts empty)
    curr = head
    while curr:
        nxt = curr.next   # SAVE the next node BEFORE we clobber curr.next,
                          # or we'd lose access to the rest of the list.
        curr.next = prev  # flip the pointer to face backward
        prev = curr       # advance prev into the reversed portion
        curr = nxt        # advance curr to the saved next node
    return prev           # prev is the new head (old tail)