Sets & Dictionaries

Sets & Dictionaries | Algoryva

Intuition

A coat check

At a coat check you hand over your coat and get a numbered ticket. Later you hand over the ticket and the attendant walks straight to the right hook, without looking through every coat. That is the whole idea of a hash table.

A set is a coat check that only remembers *whether* something is checked in. A dictionary also remembers *what belongs with it*: a key (the ticket) leading to a value (the coat).

First, the naive way

Searching a list every time

Task: given two lists, find the values that appear in both. The first idea is to take each item of the first list and ask whether it is in the second list.

Asking x in b on a list scans it from the start until it finds x or runs out. Doing that for every item of a means up to len(a) × len(b) comparisons: for two lists of 100,000 items, about 10 billion.

python

def common_naive(a, b):
    out = []
    for x in a:
        if x in b:          # scans the whole list b every time
            out.append(x)
    return out

print(common_naive([1, 2, 3, 4], [3, 4, 5]))   # [3, 4]

Cost: O(n × m): every lookup in a list costs O(m).

The concept

Sets and dictionaries

Both are built on the same trick (hashing), so they share the same rules and speed.

Set {1, 2, 3}: a collection of distinct items with no order. Adding a duplicate does nothing. Built for “is x in here?”.
Dictionary {"ana": 31}: maps each key to a value. Keys are distinct; values can repeat. Built for “what goes with this key?”. Since Python 3.7 it remembers insertion order.
Hashable: keys and set members must be hashable, meaning immutable-like: numbers, strings, tuples of those. Lists, sets and dictionaries are not hashable.
Set algebra: | union, & intersection, - difference, ^ items in exactly one set.
Speed: adding, removing and testing membership are O(1) on average, compared with O(n) for a list.

The observation

Compute the address from the key

A list finds an item by *position*; you must already know where it is. A hash table computes a position from the item itself: a *hash function* turns the key into a number, and that number (reduced to the table's size) says which bucket to look in. Insert and look-up use the same calculation, so they land in the same place.

Different keys sometimes land in the same bucket: a collision. The table copes by keeping a short list in the bucket and checking its few entries. If the hash function spreads keys well, buckets stay short, so a look-up touches only a handful of items regardless of how many are stored.

See it move

A toy hash table

Five buckets. The toy hash adds the letter codes of the key and takes the remainder mod 5. Watch each key go to its bucket, see one collision, then see two look-ups: one that finds its key after a short scan, and one that proves a key is absent. Python's real hash is far better mixed, but the mechanism is the same.

Worked by hand

The toy table by hand

The hash of a key is the sum of its letter codes mod 5.

key	letter codes sum	mod 5	bucket
cat	99 + 97 + 116 = 312	2	2
dog	100 + 111 + 103 = 314	4	4
owl	111 + 119 + 108 = 338	3	3
hen	104 + 101 + 110 = 315	0	0
ant	97 + 110 + 116 = 323	3	3 (collides with owl)

1
Look up “ant”
Hash to bucket 3. The bucket holds owl, then ant: two comparisons, found.
2
Look up “cow”
Hash to bucket 4. It holds only dog, which is not cow, so cow is absent after one comparison. We never touched the other buckets.

Implementation

Sets in code

Sets shine for removing duplicates, testing membership, and comparing groups.

python

a, b = {1, 2, 3, 4}, {3, 4, 5}
print(sorted(a | b))   # [1, 2, 3, 4, 5]
print(sorted(a & b))   # [3, 4]
print(sorted(a - b))   # [1, 2]
print(sorted(a ^ b))   # [1, 2, 5]
print(3 in a, 9 in a)   # True False
print(len(set([1, 1, 2, 2, 3])))   # 3
print(sorted(set("banana")))   # ['a', 'b', 'n']
a.add(10)
a.discard()
a.()
((a))   
(a.({, , , , }))

Implementation

Dictionaries in code

A dictionary maps keys to values. d[key] reads a value (and raises KeyError if the key is missing); d.get(key, default) is the safe version.

python

ages = {"ana": 31, "ben": 25}
ages["cy"] = 40
print(ages["ben"], ages.get("zed"), ages.get("zed", 0))   # 25 None 0
print(len(ages), "ana" in ages, "zed" in ages)   # 3 True False
print(list(ages.items()))   # [('ana', 31), ('ben', 25), ('cy', 40)]
del ages["ben"]
print(list(ages))   # ['ana', 'cy']
ages["ana"] += 1
print(ages["ana"])   # 32
try:
    print(ages[])
 KeyError:
    ()

Implementation

Counting and grouping

The two most common dictionary jobs: counting how often each item appears, and grouping items under a shared key.

python

from collections import Counter, defaultdict

print(Counter("banana"))   # Counter({'a': 3, 'n': 2, 'b': 1})
print(Counter("banana").most_common(1))   # [('a', 3)]

freq = {}
for ch in "banana":
    freq[ch] = freq.get(ch, 0) + 1
print(freq)   # {'b': 1, 'a': 3, 'n': 2}

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
groups = defaultdict(list)
for w in words:
    groups["".join(sorted(w))].append(w)
print(list(groups.values()))

Complexity

Why average O(1), and what could go wrong

The trade-off is memory: a hash table uses more space than a list for the same items, and it gives up order (for sets) in exchange for speed.

add, remove, x in s for set or dict

time O(1) averagespace O(n)

Hash the key, jump to its bucket, and compare a few entries.

worst case of those operations

time O(n)space -

If many keys collided into one bucket, look-ups would scan a long list. Python randomises string hashing, but integers hash to themselves, and some contest tests are built to make integer keys collide. A common defence is to XOR every key with one random constant.

x in some_list

time O(n)space O(1)

A list has to scan.

Iterate over a set or dict

time O(n)space O(1)

Visit each stored entry once.

Building a set or dict from n items

time O(n) averagespace O(n)

n inserts at O(1) each.

Set union / intersection of sizes n and m

time O(n + m)space O(n + m)

Each element is hashed and tested once.

Edge cases

Unhashable key{[1, 2]: 3} raises TypeError. Use a tuple (1, 2) or convert to a string.
Missing keyd[k] raises KeyError. Use d.get(k, default) or check k in d first.
Changing a dictionary while looping over itAdding or removing keys during iteration raises RuntimeError. Loop over list(d) or build a new dictionary.
Empty set{} is an empty dictionary, not an empty set. Write set().
Order of a setNot guaranteed. Sort when you need a stable order for output.
Equal numbers of different types1, 1.0 and True hash equally, so they are the same key. Be careful when mixing types.

Common mistakes

Mistakes to avoid

Testing membership in a list inside a loop.
Convert the list to a set once (s = set(a)) and test x in s.
Writing {} and expecting a set.
{} is a dictionary. Use set() for an empty set.
Reading a missing key with brackets.
Use .get(k, default) or defaultdict/Counter.
Relying on a set's printed order.
Use sorted(s) when order matters.
Using a list as a key.
Convert it to a tuple first.

Recognize it in a contest

How to spot a set or dictionary problem

Reach for it when the problem says or implies

The problem asks “have I seen this before?”, “is there a duplicate?”, “which items are in both?”: a set.
You must count how many times each thing occurs: Counter or a dictionary.
You need to look something up by name or key repeatedly: a dictionary.
You need to group items by a shared property (anagrams, same length, same remainder): a dictionary of lists.
An O(n²) nested loop only exists to search for a partner value: a dictionary or set replaces the inner loop (the Two Sum idea).

Look elsewhere when

You need items in sorted order or ranked by position: sort a list instead.

Worked problem

Does the list contain a duplicate?

The problem

Return True if any value appears at least twice in a list.

Comparing every pair would be O(n²).
A set holds only distinct values, so if the list has duplicates the set is shorter than the list.
Compare the two lengths: one pass to build the set, O(n).

python

def contains_duplicate(a):
    return len(set(a)) != len(a)

print(contains_duplicate([1, 2, 3, 1]))   # True
print(contains_duplicate([1, 2, 3]))   # False
print(contains_duplicate([]))   # False

Takeaway. Turning a list into a set and comparing sizes is the shortest duplicate test. The lesson to remember is the pattern: *a set removes repeats, so any length difference exposes them*.

Worked problem

First unique character

The problem

Given a string, return the index of the first character that appears exactly once, or -1 if there is none.

First pass: count every character with a Counter.
Second pass: walk the string in order and return the first index whose count is 1.
Two passes, O(n) time, and the second pass keeps the original order, which a dictionary alone would not tell you.

python

from collections import Counter

def first_unique(s):
    c = Counter(s)
    for i, ch in enumerate(s):
        if c[ch] == 1:
            return i
    return -1

print(first_unique("leetcode"))   # 0
print(first_unique("loveleetcode"))   # 2
print(first_unique("aabb"))   # -1

Takeaway.

Wrap-up

Remember this

A set stores distinct items; a dictionary maps keys to values. Both look things up by hashing, in O(1) on average.
A hash function turns a key into a bucket number; a collision just means a bucket holds a short list.
Keys and set members must be hashable: numbers, strings, tuples, but not lists.
Use sets for membership and duplicates, Counter/dicts for counting, defaultdict(list) for grouping.
Replacing a list scan with a set or dictionary lookup often turns O(n²) into O(n).

Cheat sheet

Set: distinct, unordered · add, discard, in · | & - ^
Dict: d[k] (KeyError) · d.get(k, default) · d.items()
Cost: add, remove, in: O(1) average
Counting: Counter(x) · d[k] = d.get(k, 0) + 1
Grouping: defaultdict(list); groups[key].append(item)
Careful: {} is a dict · keys must be hashable · set order is not stable

Top traps to avoid

Testing membership in a list inside a loop.
Writing {} and expecting a set.
Reading a missing key with brackets.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the average cost of x in s when s is a set of n items?
2.Which of these can not be a dictionary key?
3.What does sorted({1, 2, 3, 4} & {3, 4, 5}) give?
4.What is {} in Python?
5.“Group a list of words so that anagrams end up together” is best handled with:
6.In a hash table, what is a collision?
7.Is {1, 2, 2, 3} == {3, 2, 1}?
8.With d = {'a': 1}, what does d.get('b', 0) return?
9.What is len({'a': 1, 'a': 2})?
10.What is the type of {} in Python?
11.s = {1, 2, 3}; s.discard(9); s.add(2). What is len(s)?
12.d = {}; d.setdefault('a', []).append(1); d.setdefault('a', []).append(2). What does print(d) show?
13.What does print({1, 2} | {2, 3}, {1, 2} & {2, 3}) print?
14.What does print(list({'b': 1, 'a': 2})) print?
15.Why can a tuple of numbers be a dictionary key but a list cannot?

Counting first and then scanning in original order is a very common two-pass pattern. In loveleetcode the letters l, o and e repeat; v at index 2 is the first one that does not.

Sets & Dictionaries

After this lesson you will be able to

Builds on

Unlocks

A coat check

Searching a list every time

Sets and dictionaries

Compute the address from the key

A toy hash table

The toy table by hand

Sets in code

Dictionaries in code

Counting and grouping

Why average O(1), and what could go wrong

Edge cases

Mistakes to avoid

How to spot a set or dictionary problem

Does the list contain a duplicate?

First unique character

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up1 problem

Core1 problem

Application1 problem

Reading the code

Reading the code

Reading the code