Patterns

Arrays and hashing

Arrays are the default shape of interview input: an ordered collection you can index. Hash maps are the default way to remember a fact about that collection in constant time. Together they replace a lot of nested loops. This page teaches the move with original examples. They are not assessment questions, and they are not copied from a public problem statement.

Use a map when the slow version of your idea is "for each item, scan the rest of the items to find a partner." The scan is honest and often fine for tiny n. The map is the same idea with a better memory. If you cannot explain the slow idea, do not reach for the map yet. The time management notes are about finishing the honest version first when the constraints allow it.

Frequency maps

A frequency map answers "how many times has this value appeared?" You build it with one pass. The earliest moment a count hits a threshold is a useful variant, because it forces you to decide while you scan instead of after a full sort.

Original task: a lab logs badge scans in order. Return the index of the scan where some badge is seen for the k-th time. If that never happens, return None. k is at least 1.

def earliest_kth_scan(scans: list[str], k: int) -> int | None:
    seen: dict[str, int] = {}
    for index, badge in enumerate(scans):
        seen[badge] = seen.get(badge, 0) + 1
        if seen[badge] == k:
            return index
    return None


assert earliest_kth_scan(["a", "b", "a", "a"], 3) == 3
assert earliest_kth_scan(["a", "b", "a"], 3) is None
assert earliest_kth_scan([], 1) is None

One pass visits each scan once, so the time is linear in the number of scans. The map holds one entry per distinct badge, so the extra space is proportional to the number of unique badges, not to k. Returning at the first hit matters: if you kept scanning you would still be correct, but you would do extra work and you might accidentally return a later index.

Edges worth writing down before you code this family of problems: an empty log, k equal to 1 (the first scan of anything qualifies), and a log where several badges are close to the threshold. The comparison is == k, not >= k. Using >= still returns the same index if you return immediately, but it is a sloppier statement of the task and it will bite you if you later change the function to collect every badge that reaches k.

Index maps, or "have I seen the partner?"

The second classic move stores the index where a value occurred, not the count. You need it when the answer is a pair of positions.

Original task: a shelf holds weights in some order. Return any pair of indices whose weights add up to a limit. If no pair exists, return None. An index may not be used twice. The shelf is not sorted.

def shelf_pair(weights: list[int], limit: int) -> tuple[int, int] | None:
    index_of: dict[int, int] = {}
    for index, weight in enumerate(weights):
        need = limit - weight
        if need in index_of:
            return index_of[need], index
        index_of[weight] = index
    return None


assert shelf_pair([4, 1, 7, 3], 8) == (1, 2)
assert shelf_pair([4, 4], 8) == (0, 1)
assert shelf_pair([4], 8) is None

Time is linear in the number of weights. Space is linear in the worst case, because every weight might be stored before a partner appears. Insert the current weight after the lookup. If you insert first, a weight that is exactly half the limit will pair with itself. The second assert is the case people get right. The bug shows up when one item is the whole limit's half and it is the only copy.

If the shelf were sorted, two pointers would use constant extra space after the sort. That trade is the subject of the two pointers page. Say the trade in the interview: "I can sort and scan inward, or I can keep a map and stay linear without sorting. The map uses more memory." Either answer can be the right one. The weak answer is to pretend there was only one option.

Prefix sums

A prefix sum at index i is the total of every element up to i. Once you have prefixes, a subarray sum from left to right is prefix[right] - prefix[left - 1], with a zero prefix before the start. Combining prefixes with a map answers "have I seen this running total before?"

Original task: a list of daily score changes, which may be negative. Return True if some contiguous run of days sums to a target. A run may be a single day.

def has_run_sum(changes: list[int], target: int) -> bool:
    seen = {0}
    running = 0
    for change in changes:
        running += change
        if running - target in seen:
            return True
        seen.add(running)
    return False


assert has_run_sum([2, -1, 3], 4) is True
assert has_run_sum([1, 2, 3], 7) is False
assert has_run_sum([5], 5) is True

The set starts with 0 so a run that begins at the first day can succeed. Each day does a constant amount of work, so the time is linear. The set stores every running total, so the extra space is linear as well. This is the right complexity to quote. Do not say "constant space" because a set grew.

Walk [2, -1, 3] looking for 4. After 2, the total is 2, and 2 - 4 = -2 is not in {0}. After -1, the total is 1. After 3, the total is 4, and 4 - 4 = 0 is in the set. The run from the start sums to 4. The same machinery finds a run that starts later: the earlier total stored in the set is exactly the part you want to subtract.

Negative numbers are why this is not a sliding window. A window that only grows and shrinks assumes that adding an element moves the sum in a direction you can reason about. Negatives break that. If all values are positive, the sliding window page is often simpler and uses less memory. Mentioning that distinction is a good interview sentence.

What to say while you write it

Narrate the memory, not the syntax. "I am storing the index of each weight I have already passed, so the partner is a lookup instead of a scan." Then narrate the order: lookup, then insert. Then narrate complexity and one edge. Interviewers are listening for that sequence more than for a particular import.

If the prompt asks for all pairs, do not return early, and think about whether two identical values should produce one pair or many. If the prompt asks for the number of pairs, a frequency map computed in a first pass is often cleaner than an index map, because you can combine counts with arithmetic. State which one you are building so you do not mix them in one loop by accident.

Practice drill

Write all three functions from a blank file without looking. Then change each task by one word and repair the code: k-th scan becomes "return every badge that eventually reaches k"; shelf pair becomes "weights are sorted, use constant extra space"; run sum becomes "return the length of the shortest run that sums to the target" and decide whether your set still stores enough information. The third change is harder. The shortest run needs the earliest index of each total, not just whether the total existed. That upgrade is the point of the drill.

The strings page reuses frequency maps on characters. The common mistakes page covers the self-pair bug and the empty-prefix bug in shorter form. If those two feel shaky, stay on this page for another evening before you collect more patterns.