Pattern Drills

The problems in this chapter were written for this guide to drill the patterns. For each one, first run through the procedure from the earlier chapter on your own (clarify, examples, brute force, optimize) and only then read the solution. Afterwards, cover the code and write it again from scratch; that is where most of the learning happens.

Problem 1: Count ranges that sum to exactly k (prefix sums + hash map)

Daily income and spending are given as an integer array amounts (it may contain negatives). Count the contiguous ranges of days whose total is exactly k.

Example: with amounts = [1, 2, -1, 2, 1] and k = 3, the ranges are [1, 2], [2, -1, 2] and [2, 1], so the answer is 3.

Approach: Negative values break the sliding window. Let p be the running prefix sum. A range sums to k exactly when p[j] - p[i] = k, so the number of ranges ending here equals how many earlier prefix sums equal the current prefix minus k. Count prefix sums in a hash map. The key detail is seeding the map with 0 once, which represents the empty prefix.

from collections import defaultdict


def count_sum_k(amounts: list[int], k: int) -> int:
    seen = defaultdict(int)
    seen[0] = 1           # the state before adding anything
    prefix = count = 0
    for x in amounts:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count


print(count_sum_k([1, 2, -1, 2, 1], 3))  # 3
print(count_sum_k([0, 0], 0))            # 3

Complexity: O(n) time, O(n) space.

Problem 2: Count pairs with sum at most target (two pointers)

Given an integer array nums sorted in ascending order, count the pairs i < j with nums[i] + nums[j] <= target.

Example: with nums = [1, 2, 3, 4, 6] and target = 6, the pairs are (1, 2), (1, 3), (1, 4), (2, 3) and (2, 4), so the answer is 5.

Approach: Put a pointer at each end. If nums[lo] + nums[hi] <= target, every element from lo + 1 through hi can pair with lo, so count hi - lo pairs at once and advance lo. Otherwise, move hi down.

def count_pairs_at_most(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    count = 0
    while lo < hi:
        if nums[lo] + nums[hi] <= target:
            count += hi - lo
            lo += 1
        else:
            hi -= 1
    return count


print(count_pairs_at_most([1, 2, 3, 4, 6], 6))  # 5
print(count_pairs_at_most([5, 5, 5], 9))        # 0

Complexity: O(n) time (O(n log n) if you have to sort first), O(1) space.

Problem 3: Longest range with at most k distinct values (sliding window + hash map)

An access log is given as an array of user IDs, log. Find the length of the longest contiguous range that contains at most k distinct IDs.

Example: with log = ["a", "b", "a", "c", "c", "c"] and k = 2, the answer is 4, from ["a", "c", "c", "c"].

Approach: Keep a count per ID for the current window in a hash map. After adding one ID on the right, if there are more than k distinct IDs, remove from the left until there are not, deleting any ID whose count drops to 0. The size of the map is then the number of distinct IDs.

from collections import Counter


def longest_at_most_k_distinct(log: list[str], k: int) -> int:
    counts: Counter[str] = Counter()
    left = best = 0
    for right, user in enumerate(log):
        counts[user] += 1
        while len(counts) > k:
            counts[log[left]] -= 1
            if counts[log[left]] == 0:
                del counts[log[left]]
            left += 1
        best = max(best, right - left + 1)
    return best


print(longest_at_most_k_distinct(["a", "b", "a", "c", "c", "c"], 2))  # 4
print(longest_at_most_k_distinct(["x", "y"], 0))                      # 0

Complexity: O(n) time, O(k) space.

Problem 4: First ID that occurs exactly once (counting with a hash map)

Given an array of event IDs, return the earliest ID that appears exactly once in the whole array, or None if there is none.

Example: for ["k", "m", "k", "p", "m"] the answer is "p".

Approach: Count occurrences in a first pass, then scan again in the original order for the first value with count 1. Two passes are still O(n).

from collections import Counter


def first_unique(events: list[str]) -> str | None:
    counts = Counter(events)
    for event in events:
        if counts[event] == 1:
            return event
    return None


print(first_unique(["k", "m", "k", "p", "m"]))  # p
print(first_unique(["k", "k"]))                 # None

Problem 5: How many times a value occurs in a sorted array (binary search)

Given a sorted array nums, count the occurrences of x in O(log n) time.

Approach: The count is the difference between the first position holding a value at least x and the first position holding a value greater than x. The standard bisect module gives both directly. If the interviewer asks you to implement it yourself, write a lower_bound like the one below.

from bisect import bisect_left, bisect_right


def lower_bound(nums: list[int], x: int) -> int:
    lo, hi = 0, len(nums)            # the answer lies in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


nums = [1, 2, 2, 2, 5, 7]
print(bisect_right(nums, 2) - bisect_left(nums, 2))  # 3
print(lower_bound(nums, 2), lower_bound(nums, 6))    # 1 5

Summary

The five problems drill prefix sums, two pointers, variable-size sliding windows, counting and binary search. Rather than memorizing solutions, check that you can say why you picked a pattern: "negatives rule out a window", "the data is sorted, so close in from both ends". Re-solving the same problems in another language is also a good way to review.