dict and set in Practice

The workhorses

Python's dict is a production-grade hash table, and a set is the same machine storing keys with no values. Both give amortized O(1) for insert, lookup, and delete. What that means daily:

• key in d and x in s are O(1). Compare x in some_list: O(n).
• Counting, grouping, and de-duplicating all become one-pass jobs.

One rule follows from how the machine works: keys must be hashable, and every built-in immutable type is (strings, numbers, tuples of immutables). Mutable objects like lists can't be keys: if a key changed after being filed, its hash would point at the wrong bucket forever. This is the payoff of string immutability from lesson 3-1.

The tally pattern from lesson 3-2 is the single most common dict idiom:

Tallying votes

One pass to count, then a lookup-driven max, then a set to de-duplicate.

votes = ["pizza", "sushi", "pizza", "tacos", "pizza", "sushi"]

tally = {}
for v in votes:
    tally[v] = tally.get(v, 0) + 1
print(tally)

winner = max(tally, key=tally.get)
print("winner:", winner)

unique = sorted(set(votes))
print("options:", unique)

Output

{'pizza': 3, 'sushi': 2, 'tacos': 1}
winner: pizza
options: ['pizza', 'sushi', 'tacos']

tally.get(v, 0) returns 0 for a name never seen before, which is what removes the need for an explicit if-statement around the first occurrence of each option.

max(tally, key=tally.get) iterates the keys and compares them by their counts, so it returns the winning option rather than the winning number. Dropping the key argument would compare the strings themselves and return "tacos" alphabetically.

set(votes) collapses duplicates in one pass, using the same hashing machine with the values thrown away. The result is sorted before printing because sets have no reliable order, so the print order would otherwise vary.

Turning O(n²) into O(n): two sum

The classic interview question asks for the indexes of two numbers in a list that add up to a target.

Brute force checks every pair with the nested loop from lesson 1-2, which is O(n²). For 100,000 numbers that is about 5 billion comparisons.

The hash-table insight is the same scan-to-lookup move as lesson 3-2. Walk the list once, and for each number x ask whether target − x has already been seen. That question is a dict lookup, so it costs O(1) rather than an inner loop.

The bookkeeping is one dict mapping each number seen so far to its index, which is what lets the answer report positions rather than values.

One pass with one dict makes the whole thing O(n). Replacing an inner search loop with a hash lookup is the most reusable optimization in this course, and it is worth recognizing by shape: any time an inner loop is only asking does this exist, a dict or set can answer instead.

two_sum in one pass

The seen dict maps each number to its index, and the complement is checked before the current number is recorded.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([1, 2, 3], 100))

Output

[0, 1]
[1, 2]
[]

enumerate(nums) supplies both the index and the value, which matters because the answer is a pair of positions.

The order of the two statements inside the loop is deliberate. Checking target - x in seen before writing seen[x] = i prevents a number from pairing with itself, so a target of 6 against a single 3 does not return [0, 0].

Tracing [3, 2, 4] with target 6 makes the mechanism visible. seen becomes {3: 0}, then {3: 0, 2: 1}, and then x = 4 finds 6 − 4 = 2 already recorded at index 1, so the answer is [1, 2].

The last call returns [] after a full pass, which is the only case where the loop runs to completion. Every successful case exits early.

A list cannot be a dict key because it can mutate after insertion, so its hash would no longer match the bucket it was filed under.

The bucket is computed from the key's contents, as lesson 6-1 showed. Mutating the key turns the recorded bucket into a lie, because the next lookup hashes the new contents and searches somewhere else entirely.

The failure would also be silent. Nothing crashes, the entry is simply unreachable, which is a far worse outcome than an error at insertion time.

Immutable types can never go stale, which is exactly why they are the hashable ones. Strings, numbers, and tuples of immutables all have contents fixed at creation, so their hash is fixed too, and this is the practical payoff of the string immutability from lesson 3-1.

Grouping by a computed key

Counting and two sum both mapped a key to one value. The third everyday dict idiom maps a key to a group, which is SQL's GROUP BY, log lines grouped by user, and files grouped by extension, all the same move.

The mechanism turns on picking a canonical key, a value that every member of a group computes identically and non-members do not. Then a single pass with groups.setdefault(key, []).append(item) files everything at O(1) per item.

Grouping a word list into anagram families is the sharpest example. The canonical key for an anagram group is the word's letters in sorted order, so "listen", "silent", and "enlist" all reduce to "eilnst" and land under one dict key.

Note that the key has to be a string, built with "".join(...). A sorted list of letters holds the right information but cannot be a key at all, for the mutability reason from the previous block.

Grouping anagrams

Each word is filed under its sorted letters.

def group_anagrams(words):
    groups = {}
    for word in words:
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return groups

words = ["listen", "silent", "enlist", "rat", "tar", "art", "hello"]
groups = group_anagrams(words)
for key in sorted(groups):
    print(key, groups[key])

Output

art ['rat', 'tar', 'art']
ehllo ['hello']
eilnst ['listen', 'silent', 'enlist']

sorted(word) returns a list of characters, and "".join(...) fuses it back into a hashable string, which is the one line that makes the key usable.

groups.setdefault(key, []).append(word) handles both cases in a single statement, creating the group list the first time a key appears and appending to it every time after.

Words keep their arrival order inside a group, so rat, tar, art print in the order they were read. The key art is a coincidence worth noticing, since those three letters sorted happen to spell one of the words.

hello forms a group of one, which is the honest result. The function groups by the key rather than filtering for matches, so a word with no anagram partners still gets a bucket of its own.