Hash Maps & Sets

Stop searching the past. Look it up by name.

You have 100,000 transaction amounts, and you need two of them that add up to exactly 1,000. Checking every pair means n(n−1)/2 = 4,999,950,000 additions. A judge gives you a second or two.

Now watch what the slow version actually does. When it reaches an amount of 380, it scans everything before it for one specific number: 620. It isn't comparing anything interesting. It's searching for a value it can name in advance. A dictionary answers "is 620 here, and where?" in expected constant time, so the whole job becomes one pass and 100,000 lookups.

In the foundation lesson the thing you looked up was the value itself ("have I seen 7 before?"). This lesson generalizes that move. The key you look up can be the value's partner (target − x), a signature shared by a whole group (the sorted letters of a word), or a running total (prefix − k). Almost every hash problem comes down to one design decision:

Decide what question each element asks about the past. Then store the past keyed by the answer to that question.

Before you start: this lesson builds on Foundation: Arrays & Strings. You should already know the "seen set" for duplicates, 26-slot count vectors for anagrams, output contracts, and the prefix-sum formula sum(l..r) = prefix[r + 1] − prefix[l]. Those ideas are used here without re-teaching them.

How a dictionary finds things (and when it can't)

You don't need to build a hash table in an interview. You do need an accurate picture of one, because that picture tells you what "O(1)" promises, which keys are legal, and how a correct-looking solution can quietly go quadratic.

Slots, collisions, probing

A Python dict keeps an array of slots, and a set works the same way without the values (CPython tunes the two differently, as you'll see). To store a key, Python computes hash(key), an integer, and turns it into a starting slot. For a table of 8 slots, think hash(key) % 8. Small integers hash to themselves, which makes them handy for a picture:

8 slots. Start slot = hash(key) % 8. Illustration uses "try the next slot".

insert 13 → 13 % 8 = 5 → slot 5 empty                      → store in 5
insert 22 → 22 % 8 = 6 → slot 6 empty                      → store in 6
insert 29 → 29 % 8 = 5 → 5 holds 13, 6 holds 22, 7 empty  → store in 7

slot:   0     1     2     3     4     5     6     7
      [   ] [   ] [   ] [   ] [   ] [13 ] [22 ] [29 ]

lookup 29: slot 5 (13, no) → 6 (22, no) → 7 (29, yes)             found
lookup 37: slot 5 (13) → 6 (22) → 7 (29) → 0 (empty)             not present

Two different keys wanting the same slot is a collision, and collisions are normal. Tables resolve them in one of two ways. Chaining hangs a small list off each slot; Java's HashMap works this way. Open addressing probes other slots by a fixed rule until it finds the key or an empty slot; CPython's dict and set work this way. CPython's real probe order isn't simply "next slot": a dict jumps around the table, and a set checks a few neighbouring slots before jumping. The picture is the same either way: a lookup is short as long as the probe sequences are short.

Each stored entry keeps its full hash. A probe calls == on an entry only when the full hashes match. (A dict also accepts an entry that is the very same object before looking at hashes; a set checks the hash first.) Hold on to that detail; it explains the rules for keys below.

Why "O(1)" is an expected cost

Probe sequences stay short for two reasons:

• The table never gets crowded. CPython keeps a dict at most about two-thirds full. When an insert would pass that point, it allocates a table roughly twice as large and re-inserts every entry. (A set uses a lower fill limit and grows faster while small; the argument is the same.) That resize costs O(n), but the next one waits until the bigger table fills up, so the re-insert work over all resizes is a geometric series: n + n/2 + n/4 + … < 2n. Spread over n inserts, that is amortized O(1) per insert.
• Good hashes scatter keys. Different keys usually start at different slots.

The second reason is an assumption, not a guarantee. You can break it on purpose and count the damage:

class Key:
    eq_calls = 0
    def __init__(self, v):
        self.v = v
    def __eq__(self, other):
        Key.eq_calls += 1
        return self.v == other.v
    def __hash__(self):
        return 42                        # every key collides

for n in (1000, 2000, 4000):
    Key.eq_calls = 0
    table = {}
    for i in range(n):
        table[Key(i)] = i
    print(n, Key.eq_calls)

1000 500300
2000 2000800
4000 8000531

Every new key has to be compared with every key already stored, so n inserts make roughly n²/2 comparisons. Double n and the work quadruples: the dict has quietly become a list you search from the front. Change __hash__ to return hash(self.v) and the same run makes 0 calls to __eq__, because different full hashes never need an == check.

So the honest statement is: dict and set operations cost expected O(1) time, and O(n) in the worst case, when many keys collide. Built-in hashes make that worst case rare. Python also salts str hashes with a random value per process, so hash("abc") changes between runs and outsiders can't easily aim collisions at your string keys. Integers are not salted: hash(12345) == 12345. Complexity claims in this lesson therefore say "expected".

One more cost hides in the key itself. Hashing a string or tuple of length k takes O(k) time, and so does comparing two of them. (A str caches its hash after the first time, but a fresh string, such as a new slice, pays again, and a successful lookup still compares all k characters.) "O(1) per lookup" means O(1) for small keys such as integers. With 30-letter string keys, a lookup does work proportional to 30, not 1.

What can be a key

Predict first: this code stores a grid cell in a set and then moves the cell. What does the last line print?

class Cell:
    def __init__(self, r, c):
        self.r, self.c = r, c
    def __eq__(self, other):
        return (self.r, self.c) == (other.r, other.c)
    def __hash__(self):
        return hash((self.r, self.c))

cell = Cell(0, 0)
visited = {cell}
cell.r = 5
print(cell in visited, Cell(0, 0) in visited, Cell(5, 0) in visited, len(visited))

The rules follow from the slot picture:

1. A key must not change while it is stored. Its hash decided where it lives. int, float, str, bytes, frozenset and tuples of hashable things are hashable. list, set and dict are not, and using one as a key raises TypeError ("unhashable type"). That includes a tuple that contains a list: hash((1, [2])) fails.
2. Equal keys must have equal hashes. The table compares hashes before it calls ==, so two "equal" objects with different hashes would be stored as different keys. Python keeps this promise for its own types, even across types: 1 == 1.0 == True, and {1: 'a', 1.0: 'b', True: 'c'} is {1: 'c'}, a single key.
3. Your own classes: base __eq__ and __hash__ on the same fields, and don't change those fields afterwards. @dataclass(frozen=True) writes both methods for you and forbids the mutation. If you define __eq__ without __hash__, Python makes instances unhashable.

For LeetCode, the practical rule is: turn lists into tuples, sets into frozensets, and multi-part keys into tuples. A grid cell is (r, c), not str(r) + str(c). That string version gives the cells (1, 23) and (12, 3) the same key, "123".

Your turn: a grid solver with 20 columns stores visited cells under the integer key r * 10 + c. Find a cell that collides with (1, 13). Then give two key formulas that can never collide.

The Python toolkit

Four behaviours cause a lot of hash-table bugs:

• Reading a defaultdict inserts. if g[k]: on a missing k adds k. That changes len(g), and if you are looping over g at the time, the next step raises RuntimeError: dictionary changed size during iteration. Use k in g when you only want to ask.
• Don't add or remove keys while iterating over a dict or set. Updating the values of existing keys is fine. To delete, loop over list(d), or build a new dict.
• d.get(k) returns None for a missing key, and a stored 0 is falsy too. if d.get(k): cannot tell "absent" from "stored at index 0". Test with k in d or is not None.
• Order: a dict remembers insertion order. The language has guaranteed that since Python 3.7, so list(dict.fromkeys(items)) is a legitimate order-preserving dedupe. A set has no guaranteed order: {10, 1, 5, 100, 3} may iterate as 1, 3, 100, 5, 10.

Set or dict? Use a set when the only question is "is x here?". Use a dict when you need something about x: where it was, how many times, which group. Choose for the question you're asking, not for memory. In CPython a set of n keys is not reliably smaller than a dict with the same keys.

Move 1: Count first, decide second

Smell: the answer depends on how often something appears in the whole input, so no single left-to-right glance can decide it.

Take LeetCode 387: First Unique Character in a String: return the index of the first character that appears exactly once, or −1.

Predict first: can you solve "loveleetcode" in a single left-to-right pass that keeps only a set of characters seen so far?

The slow version calls s.count(ch) for every position. Each call scans the whole string, so that's O(n²). What it repeats: the same totals, recomputed for every position. Compute them once:

from collections import Counter

def first_uniq_char(s):
    counts = Counter(s)            # pass 1: totals
    for i, ch in enumerate(s):     # pass 2: first one with total 1
        if counts[ch] == 1:
            return i
    return -1

On "loveleetcode" the totals are e: 4, l: 2, o: 2, and 1 for each of v, t, c, d.

Two passes of O(n) each, so O(n) expected time. The extra space is O(σ), where σ is the number of distinct characters (at most 26 when the input is lowercase letters). With a known small alphabet, the 26-slot array from the foundation lesson does the same job. Reach for Counter when the keys are words, large integers or tuples.

Why it works. After pass 1, counts[ch] is the total number of occurrences of ch, which is exactly the fact a single pass lacked. Pass 2 walks positions in order, so the first position that passes the test is the first unique character.

Traps.

• max(counts, key=counts.get) finds a most frequent item, but it raises ValueError on an empty dict. Decide what empty input should return.
• counts.most_common(k) sorts by count, and ties keep first-seen order. Frequency ranking (top k) is a heap problem; see Heaps & Priority Queues.

Your turn: LeetCode 884: Uncommon Words from Two Sentences. A word is uncommon if it appears exactly once in one sentence and not at all in the other. For s1 = "this apple is sweet" and s2 = "this apple is sour" the answer is ["sweet", "sour"]. What single condition replaces "exactly once here and nowhere there"?

from collections import Counter

def uncommon_from_sentences(s1, s2):
    counts = Counter(s1.split()) + Counter(s2.split())
    return [w for w, c in counts.items() if c == 1]

Move 2: Look up your partner

Smell: a nested loop where the inner loop searches for a specific value that the outer element determines. For a pair sum, that value is target − x.

LeetCode 1: Two Sum: return the indices of the two numbers that add up to target. Exactly one answer exists, and you may not use the same element twice. The array can hold up to 10⁴ numbers, so checking all pairs means up to 49,995,000 of them.

Predict first: this one-pass attempt registers each number before looking for its partner. What does it return for nums = [3, 2, 4], target = 6?

def two_sum_eager(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        seen[x] = i                        # register first...
        if target - x in seen:             # ...then look
            return [seen[target - x], i]
    return []

The slow version and what it repeats

def two_sum_slow(nums, target):
    for j in range(len(nums)):
        for i in range(j):                 # search the past...
            if nums[i] == target - nums[j]:
                return [i, j]
    return []

For each j, the inner loop searches the past for one value it could name in advance, target − nums[j]. A search by value is exactly what a dictionary replaces.

The fast version

def two_sum(nums, target):
    seen = {}                      # value -> index where it appeared
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:           # 1. look for the partner
            return [seen[need], i]
        seen[x] = i                # 2. then register yourself
    return []

Trace nums = [4, 11, 7, 2, 15], target = 9:

Expected O(n) time and O(n) extra space, for n = len(nums). That trade (memory for time) is the usual price of hashing.

Why it works. The invariant: before index i is processed, seen holds every value among nums[0..i−1], each with an index where it occurs. Take any valid pair j < i. When the loop reaches i, nums[j] is already in seen, so the pair is found at its later element. Checking before registering means seen never contains the current element, so the partner is always a different index.

Store what you are, look up what you need. The dict's keys are values you have seen. The lookup asks for the value you need. (The mirror design, storing each element's need and checking whether x is in it, also works. Mixing the two does not.)

Traps and edge cases.

• Duplicates. [3, 3] with target 6 works: the first 3 is stored before the second one looks. A later duplicate overwrites the stored index. That's harmless here, but if a variant wants the earliest index, use seen.setdefault(x, i).
• "Is it there?" versus "what is stored?" j = seen.get(need) followed by if j: skips a partner at index 0, because 0 is falsy. Test with need in seen, or j is not None.
• Sorted input and O(1) extra space. Then two pointers from both ends need no dict at all; see Two Pointer Techniques. Sorting an unsorted array just to use two pointers loses the original indices unless you carry them along.
• Several possible partners. If a pair "works" when the sum is any power of two, or when the difference is exactly k, look up each candidate partner. That's a few lookups per element instead of one.

Plot twist: which pairs are you counting?

"Count the pairs that sum to 4" in [2, 2, 2, 2] has three different correct answers, depending on the contract:

A plain set of seen values returns 3 here, which answers none of the three. It knows whether a 2 appeared, not how many did.

For index pairs, add how many partners are already waiting, then register yourself:

def count_pairs(nums, target):
    counts = {}
    pairs = 0
    for x in nums:
        pairs += counts.get(target - x, 0)   # every earlier partner makes a pair
        counts[x] = counts.get(x, 0) + 1
    return pairs

Each pair is counted exactly once, at its later element: 0 + 1 + 2 + 3 = 6. To count pairs with equal keys instead (nums[i] == nums[j]), look up x itself rather than target − x.

For disjoint pairs, a match consumes the waiting partner:

def max_operations(nums, k):
    waiting = {}                              # value -> unmatched copies
    ops = 0
    for x in nums:
        if waiting.get(k - x, 0) > 0:
            waiting[k - x] -= 1               # use up one partner
            ops += 1
        else:
            waiting[x] = waiting.get(x, 0) + 1
    return ops

Both run in expected O(n) time with O(n) extra space. 3Sum is Two Sum inside a loop: fix one element, then find a pair in the rest, which is O(n²) overall. Removing duplicate triplets is much easier after sorting, so that problem lives in Two Pointer Techniques.

Your turn: LeetCode 2006: Count Number of Pairs With Absolute Difference K. Count pairs i < j with |nums[i] − nums[j]| == k, where k ≥ 1. Write it in one pass. Predict the results for [1, 2, 2, 1] with k = 1 and for [3, 2, 1, 5, 4] with k = 2. Then: what would your function return for [1, 1] with k = 0, and why?

def count_pairs_abs_diff(nums, k):
    counts = {}
    pairs = 0
    for x in nums:
        pairs += counts.get(x - k, 0) + counts.get(x + k, 0)
        counts[x] = counts.get(x, 0) + 1
    return pairs

Move 3: Design the key

Smell: "group together the items that are equivalent", or "are these two the same up to X?". The slow code compares each item with every group formed so far.

LeetCode 49: Group Anagrams: given ["eat", "tea", "tan", "ate", "nat", "bat"], return the groups [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] in any order.

Predict first: which of these keys puts two words in the same group exactly when they are anagrams?

1. frozenset(w)
2. sum(ord(ch) for ch in w)
3. sorted(w)
4. "".join(sorted(w))

Slow, then fast

The slow approach keeps a list of groups and checks each word against one representative per group with an anagram test. With g groups that is O(g · k) per word, where k is the word length. When most words are unrelated, g grows toward n, and the total approaches O(n² · k).

What it repeats is the question "which group is mine?", asked by comparing. Replace the comparison with a canonical key: a value that every member of a group shares and no outsider has. Then the dict finds your group in one lookup:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

The groups come out in first-seen order because dicts keep insertion order. LeetCode accepts any order anyway. The empty string is a legal word: its key is "", and it forms its own group.

Why it works. A key function f groups correctly exactly when f(a) == f(b) if and only if a and b belong together. The key can fail in two directions:

Sorted letters pass both tests. Two words are anagrams exactly when they have the same letters with the same multiplicities, and sorting keeps the multiplicities while forgetting the order.

A second key: the count vector

The foundation lesson's 26-slot count vector is also an exact anagram signature. Turn it into a tuple to make it hashable:

def anagram_key(w):
    counts = [0] * 26
    for ch in w:
        counts[ord(ch) - ord('a')] += 1
    return tuple(counts)

For n words of length at most k, sorted keys cost O(n · k log k) time and count keys cost O(n · (k + 26)). Both use O(n · k) space for the groups. The asymptotic winner is not always the stopwatch winner. In one CPython 3.14 run on 2,000 random words, sorted keys were faster up to about 15 letters (sorting runs in C, while the count loop runs in Python), and count keys pulled ahead from about 25 letters. Either answer is fine in an interview if you state the costs correctly.

Your turn: LeetCode 205: Isomorphic Strings. Two strings are isomorphic if you can replace characters one-for-one (a bijection) to turn one into the other: "egg" and "add" are, "foo" and "bar" are not, "paper" and "title" are. Design a key shape(s) so that two strings are isomorphic exactly when their shapes are equal. What is shape("paper")?

def shape(s):
    first = {}                                   # char -> order of first appearance
    return tuple(first.setdefault(ch, len(first)) for ch in s)

def is_isomorphic(s, t):
    return len(s) == len(t) and shape(s) == shape(t)

Move 4: Prefix sums meet a dictionary

Smell: count (or find the longest) contiguous subarray with an exact sum property, and the numbers can be negative.

LeetCode 560: Subarray Sum Equals K: count the contiguous subarrays of nums whose sum is exactly k. There are up to 2 × 10⁴ numbers, each between −1000 and 1000.

Predict first: how many subarrays of [1, −1, 1, −1] sum to 0?

Why a window doesn't work

With only positive numbers you could slide a window, growing it while the sum is below k and shrinking it while the sum is above k (see Sliding Window Patterns). Negatives break the rule the window depends on: adding an element can make the sum smaller. So "too big, shrink" and "too small, grow" stop being safe moves. The brute force checks every (start, end) pair, which is 200,010,000 subarrays when n = 2 × 10⁴.

From the prefix formula to a lookup

From the foundation lesson: with prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i],

sum(l..r) = prefix[r + 1] − prefix[l]

Fix the right end r. The subarray l..r sums to k exactly when prefix[l] = prefix[r + 1] − k. So as you sweep r to the right, the question is: how many earlier prefix sums equal current − k? That's a counting lookup. Keep a dict from prefix value to how many times it has occurred:

def subarray_sum(nums, k):
    seen = {0: 1}              # the empty prefix: sum 0, seen once
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)     # subarrays ending here
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Trace nums = [1, 2, −2, 2, 2, 1], k = 3:

The last row finds two subarrays at once. Prefix 3 occurred after index 1 and after index 3, so both [−2, 2, 2, 1] (indices 2–5) and [2, 1] (4–5) end here with sum 3. The other two are [1, 2] and [1, 2, −2, 2]. Total 4.

Why it works. The invariant: when index r is processed, seen[v] is the number of boundaries l in 0..r with prefix[l] = v. Every subarray has exactly one right end, and it is counted once, at that end. Expected O(n) time. The extra space is O(n), one entry per distinct prefix value.

Three traps, three wrong answers:

• Forgetting {0: 1}. prefix[0] = 0 is a real boundary, the start of the array. Without it, subarrays that start at index 0 are missed: [1, 2, 3] with k = 3 gives 1 instead of 2.
• Registering before looking. If you add the current prefix before the lookup, then when k = 0 every prefix matches itself, and you count an empty subarray at each step. [1, −1, 1, −1] with k = 0 gives 8 instead of 4.
• A set instead of counts. Repeated prefix values are the whole point: the last row of the trace needed the number 2, not "yes".

The longest version: keep the first index

To find the longest subarray with a property, store the earliest index at which each prefix value occurs. For a fixed right end, the longest subarray starts at the leftmost matching boundary.

LeetCode 525: Contiguous Array asks for the longest subarray of a binary array with equally many 0s and 1s. Count 1 as +1 and 0 as −1. Then "equal counts" means "sum 0", which means "two equal running balances":

def find_max_length(nums):
    first = {0: -1}                 # balance -> earliest index; empty prefix at -1
    balance = 0
    best = 0
    for i, x in enumerate(nums):
        balance += 1 if x == 1 else -1
        if balance in first:
            best = max(best, i - first[balance])
        else:
            first[balance] = i      # only the first occurrence is kept
    return best

Trace [1, 0, 1, 1, 1, 0, 0]:

The answer is 6: indices 1–6, [0, 1, 1, 1, 0, 0]. Two details decide it. The base entry is {0: -1} (an index, not a count), so row 1 can measure from before the array. And the else keeps the first index. Overwrite it with every new index and row 6 measures from index 2, returning 4.

Range-sum queries on a fixed array need no dict at all. They belong to Prefix, Suffix & Range Updates.

Your turn: LeetCode 974: Subarray Sums Divisible by K. Count the subarrays whose sum is divisible by k. nums = [4, 5, 0, −2, −3, 1], k = 5 should give 7. What should the key be, what is the base entry, and what changes if you port the solution to Java?

def subarrays_div_by_k(nums, k):
    seen = {0: 1}
    rem = 0
    count = 0
    for x in nums:
        rem = (rem + x) % k           # Python: always in 0..k-1 for k > 0
        count += seen.get(rem, 0)
        seen[rem] = seen.get(rem, 0) + 1
    return count

Move 5: Sets that ask "is my neighbour here?"

Smell: the question is about which values exist near each other, positions don't matter, and sorting is too slow or not allowed.

LeetCode 128: Longest Consecutive Sequence: return the length of the longest run of consecutive integers that appear in the array, in any order. The algorithm must run in O(n) time. n goes up to 10⁵ and values up to ±10⁹.

Predict first: what are the answers for [100, 4, 200, 1, 3, 2] and for [1, 2, 2, 3]? Would sorting meet the requirement?

The other slow idea walks upward from every value: from 1 it walks 1, 2, 3, 4, then from 2 it walks 2, 3, 4 again, and so on. A run of length L costs about L²/2 steps. What repeats is walking the same run from its middle. So only start walking where a run begins, at an x whose x − 1 is absent:

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:              # iterate the set, not nums
        if x - 1 in values:       # not a run start; its run is walked elsewhere
            continue
        length = 1
        while x + length in values:
            length += 1
        best = max(best, length)
    return best

On [100, 4, 200, 1, 3, 2]:

The set may hand you the values in any order; the result is the same. The answer is 4.

Why it's O(n) despite the nested loop. A nested loop is not automatically O(n²); count the work. Every distinct value belongs to exactly one run, and each run is walked exactly once, from its start. So the inner while makes at most u successful steps in total, where u is the number of distinct values. The outer loop runs u times. Building the set is O(n). That gives expected O(n) time and O(u) extra space.

⚠️ Iterate the set, not nums. With duplicates, looping over nums visits a run start once per copy and walks the whole run each time. Take m copies of 1 followed by 1, 2, …, m. Iterating the set takes m − 1 walking steps. Iterating the list takes m² − 1. With m = 4,000 that was 3,999 steps against 15,999,999 in a real run, and at LeetCode's n = 10⁵ it would be about 2.5 billion.

Sets also do algebra. For LeetCode 349: Intersection of Two Arrays, list(set(a) & set(b)) is the whole solution: expected O(len(a) + len(b)) time. |, - and ^ give union, difference and symmetric difference.

Your turn: LeetCode 202: Happy Number. Replace n by the sum of the squares of its digits, and repeat. n is happy if this reaches 1. Otherwise it loops forever through a cycle that doesn't contain 1. Decide is_happy(19) and is_happy(2). How do you know when to stop?

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1

When a hash table is the wrong tool

A dict is the default answer to "search the past by value", but not the only one. Check the constraints before you reach for one.

No dict needed: the array is its own hash table

LeetCode 442: Find All Duplicates in an Array: n integers, each in [1, n], each appearing once or twice. Return the ones that appear twice, in O(n) time and O(1) extra space besides the output.

A value v can be sent to index v − 1. That is a perfect "hash function": no two values share a slot, and it covers exactly the array's own indices. Use the sign of nums[v − 1] as the "seen v" bit:

def find_duplicates(nums):
    dups = []
    for x in nums:
        slot = abs(x) - 1          # abs: the value may already carry a mark
        if nums[slot] < 0:
            dups.append(abs(x))    # second visit to this slot
        else:
            nums[slot] = -nums[slot]
    return dups

[4, 3, 2, 7, 8, 2, 3, 1] returns [2, 3]. The contract matters here. This solution mutates the input (you can restore it afterwards with abs), and it depends on values being exactly 1..n: an array of length n that contained the value n + 1 would index past the end. LeetCode 287: Find the Duplicate Number forbids modifying the array, and its standard solution is fast/slow cycle detection instead.

A dict keyed by function arguments is also how memoization caches results. Dynamic Programming Mastery builds on that.

Final round: no label on the problem

Each problem below needs one of this lesson's moves, possibly with a twist. Name the question each element asks, then choose the key.

Challenge 1: Contains Duplicate II

LeetCode 219: Contains Duplicate II: return True if two different indices i and j have nums[i] == nums[j] and |i − j| ≤ k. [1, 2, 3, 1] with k = 3 → True. [1, 2, 3, 1, 2, 3] with k = 2 → False.

1. What does each element need to know about the past?
2. If a value appeared several times before, which earlier index is the only one worth remembering?
3. Predict [1, 0, 1, 1] with k = 1.

def contains_nearby_duplicate(nums, k):
    last = {}
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i                 # overwrite: the latest index is the useful one
    return False

Challenge 2: Pairs of songs

LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60: count pairs i < j with (time[i] + time[j]) % 60 == 0. [30, 20, 150, 100, 40] → 3. [60, 60, 60] → 3. n goes up to 6 × 10⁴.

1. Which move is this, and what replaces "the partner value"?
2. What partner does a song whose duration is a multiple of 60 need?
3. Why is a dict not even necessary?

def num_pairs_divisible_by_60(time):
    counts = [0] * 60
    pairs = 0
    for t in time:
        r = t % 60
        pairs += counts[(60 - r) % 60]   # earlier songs that complete this one
        counts[r] += 1
    return pairs

Challenge 3 (boss level): four arrays

LeetCode 454: 4Sum II: four arrays a, b, c, d, each of length n ≤ 200. Count the tuples (i, j, k, l) with a[i] + b[j] + c[k] + d[l] == 0. For a = [1, 2], b = [−2, −1], c = [−1, 2], d = [0, 2] the answer is 2.

Four nested loops make 200⁴ = 1.6 billion checks. Where can a lookup replace work? What does it cost in memory?

from collections import Counter

def four_sum_count(a, b, c, d):
    ab = Counter(x + y for x in a for y in b)       # sum -> number of (i, j) pairs
    return sum(ab[-(x + y)] for x in c for y in d)  # Counter returns 0 if missing

Cheat sheet: what does the element ask?

Every row costs expected O(1) per lookup for small keys, O(k) for keys of length k, and O(n) extra space unless the key range is bounded.

Before moving on, take one problem from this lesson, open a blank editor, and explain it out loud. Say what each element asks about the past. Say what the dict stores, and what it holds right before index i is processed. Say why it's a dict and not a set (or the other way round), and what the base entry means. Then name the input that breaks the most tempting wrong version. If you can do that for Two Sum, Group Anagrams and Subarray Sum Equals K, you have the core of this lesson.

Next: Prefix, Suffix & Range Updates takes prefix sums beyond lookups, to range queries and difference arrays. Later, Dynamic Programming Mastery caches results in dicts, Heaps & Priority Queues turns counts into top-k answers, and String Algorithms hashes whole substrings with rolling hashes. Revisit Sliding Window Patterns and Longest Substring Without Repeats to see a count table and a last-seen-index map drive a moving window.