Python says my list can’t be a dict key

New to dicts and sets? Open a quick recap. It takes about two minutes.

Quick recapDicts and sets in two minutes· 2 min

A dict maps keys to values. A set holds each value once. Both find an item by its value in one step, without searching.

ages = {"ana": 31}
ages["bo"] = 25        # add a key
"ana" in ages          # True, found in one step

seen = set()
seen.add(3)
seen.add(3)            # already there: seen is still {3}
len(seen)              # 1

See the problem

You’re building a word game. It shows which of the player’s words use exactly the same letters, like eat, tea and ate. Each word’s letters, sorted, are the same for the whole group. So you use them as the key:

groups = {}
for word in ["eat", "tea", "tan", "ate", "nat", "bat"]:
    key = sorted(word)          # ['a', 'e', 't'] for eat, tea and ate
    if key not in groups:
        groups[key] = []
    groups[key].append(word)

Python stops on the very first word:

TypeError: unhashable type: 'list'

Text works as a key, and so do numbers. Why not a list?

Define the task

• Input: words, a list of lowercase words, using only the letters a to z. It may be empty, it may repeat a word, and a word may be "".
• Output: a list of groups. Two words share a group when they use the same letters, the same number of times each. Groups come in the order their first word appears. Inside a group, words keep their order.
• The hard part: it must be quick. One test gives it 20,000 words and 3 seconds.

Example: group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) gives [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]. And "aab" and "abb" go in different groups: the same letters, but not the same number of each.

Pause and think

⏸ Pause and think

sorted(word) gives the same list for eat, tea and ate. Why won’t a dict take it as a key? What could you use instead?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

A dict needs keys that can never change. Which containers you know can’t change?

Hint 2 of 3

tuple(sorted(word)) holds the same letters, and a tuple can’t change.

Hint 3 of 3

Or count the letters: 26 numbers, one per letter. Put the counts in a tuple.

Understand the idea

Some objects can change after they’re made. Others never can.

Can change (mutable)	Can’t change (immutable)
list, dict, set	int, float, bool, str, tuple, frozenset, None

When an object can change, a change made through one name shows through every name that points to it. When it can’t, anything that looks like a change makes a new object, and only the name on that line moves to it. So s.upper() gives back new text and leaves s alone, and s += "!" points s at new text.

Now the keys. A dict files each key under a number worked out from its value, called its hash. That’s how it finds a key in one step. If a key could change, its value would change, and the dict would look for it in the wrong place. So of the built-in types, Python only takes keys that can’t change. A tuple counts only if everything inside it can’t change either. (Objects of your own classes can be keys too: by default they’re compared by identity, which never changes.)

★Key insight

A list, dict or set can change in place, and every name that points to it sees the change. Numbers, text and tuples can’t change: anything that looks like a change makes a new object. Of the built-in types, only ones that can’t change can be dict keys or set items.

Watch it happen. Names are on the left and objects on the right, as in the last lesson. The player stops to ask what happens next. Then type your own lines under it: try d = {key: 1} to see the error.

A list changes, text doesn’t

⤢ Full view

Names

none yet

Objects

no lists, dicts or tuples yet

• → #2 points to object #2
• changed by this line
• nothing points to it

Step 1 of 9. Before the first line runs, there are no names and no objects.

◀ BackPlayNext ▶Reset Ask me first Show as text

1word = 'tea'
2key = sorted(word)
3same = key
4key += ['s']
5old = word
6word += 's'
7word.upper()
8groups = {tuple(key): word}

Try your own input

Python, one line per rowword = 'tea' key = sorted(word) same = key key += ['s'] old = word word += 's' word.upper() groups = {tuple(key): word}

Use numbers, text, lists, dicts and tuples. It knows =, +=, del, print(), comparisons, slices, comprehensions, the common list methods, sorted(), list(), dict(), tuple(), range(), and copy.deepcopy() after import copy.

Show it

key += ['s'] changed list #1 itself, so same saw it. word += 's' made new text, so old kept 'tea'. The same +=, two different results.

Climb the ladder

n is the number of words, and k the length of the longest word.

Okay

No dict: search a list of keys

The idea: Keep the sorted letters of each group in a list, and search it for each word’s letters.

On the six words: eat gives ['a', 'e', 't'], which isn’t in keys yet, so it starts group 0. tea gives the same list, and letters in keys finds it with ==, so tea joins group 0. tan starts group 1, ate joins group 0, nat joins group 1, and bat starts group 2.

Lists can’t be keys, but they can be compared with ==. So this works, without any hashing.

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words that use the same letters. No dict: search a list of keys."""
    keys: list[list[str]] = []  # keys[i] is the sorted letters of groups[i]
    groups: list[list[str]] = []
    for word in words:
        letters = sorted(word)
        if letters in keys:
            groups[keys.index(letters)].append(word)
        else:
            keys.append(letters)
            groups.append([word])
    return groups

Time

O(n² · k)

Space

O(n · k)

Why

Each word may compare its letters with every group so far.

Where it breaks: speed. letters in keys checks the groups one by one. With 20,000 words that are all different, that’s about 200 million checks, far past the 3-second limit.

Better

Freeze the letters into a tuple

The idea: Use tuple(sorted(word)) as a dict key: the same letters as before, in an object that can’t change.

The waste in Okay: it searches a list of keys, because a list can’t be a key. A tuple can.

On the six words: eat gives the key ('a', 'e', 't'). tea and ate give an equal tuple, so the dict finds the same group in one step. The dict keeps groups in the order their keys were added, so the answer comes out in first-seen order.

"".join(sorted(word)), the letters as text, works just as well. Text can’t change either.

Highlighted lines are new in this rung.

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words by their sorted letters, frozen into a tuple so a dict takes them."""
    groups: dict[tuple[str, ...], list[str]] = {}
    for word in words:
        key = tuple(sorted(word))  # a list can't be a key, a tuple can
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

Time

O(n · k log k)was O(n² · k)

Space

O(n · k)

Why

Each word is sorted once, then found in the dict in one step.

What changed from the previous rung

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words that use the same letters. No dict: search a list of keys."""
    keys: list[list[str]] = []  # keys[i] is the sorted letters of groups[i]
    groups: list[list[str]] = []
    """Group words by their sorted letters, frozen into a tuple so a dict takes them."""
    groups: dict[tuple[str, ...], list[str]] = {}
    for word in words:
        letters = sorted(word)
        if letters in keys:
            groups[keys.index(letters)].append(word)
        else:
            keys.append(letters)
            groups.append([word])
    return groups
        key = tuple(sorted(word))  # a list can't be a key, a tuple can
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

Where it breaks: every word is sorted, which costs O(k log k). Long words do more work than they need to.

Best

Count the letters, then freeze the counts

The idea: Count each letter into a list of 26 numbers, then use tuple(counts) as the key.

The waste in Better: it sorts each word, when counting the letters is enough to tell the groups apart.

On the six words: eat counts one a, one e and one t. So its key is a tuple of 26 numbers: 1 in those three places and 0 everywhere else. tea and ate give the same counts. counts is a list so that += 1 can change it in place. tuple(counts) then freezes it into a key.

Highlighted lines are new in this rung.

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words by how many of each letter they have, frozen into a tuple."""
    groups: dict[tuple[int, ...], list[str]] = {}
    for word in words:
        counts = [0] * 26  # counts[0] is how many a's, counts[25] how many z's
        for letter in word:
            counts[ord(letter) - ord("a")] += 1
        key = tuple(counts)  # the list of counts can't be a key, a tuple can
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

Time

O(n · k)was O(n · k log k)

Space

O(n · k)

Why

Each word is read once, letter by letter. Every key is 26 numbers long.

What changed from the previous rung

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words by their sorted letters, frozen into a tuple so a dict takes them."""
    groups: dict[tuple[str, ...], list[str]] = {}
    """Group words by how many of each letter they have, frozen into a tuple."""
    groups: dict[tuple[int, ...], list[str]] = {}
    for word in words:
        key = tuple(sorted(word))  # a list can't be a key, a tuple can
        counts = [0] * 26  # counts[0] is how many a's, counts[25] how many z's
        for letter in word:
            counts[ord(letter) - ord("a")] += 1
        key = tuple(counts)  # the list of counts can't be a key, a tuple can
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    return list(groups.values())

When Best isn’t best: for short words, Better is often faster in practice. sorted() runs in fast C code inside Python, while Best’s loop runs one Python step per letter. Best pulls ahead as words get longer. In an interview, give Better first, then say how counting removes the sort.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it passes everything except the speed test.

Group words with the same letters

Ctrl + Enter runs

def group_anagrams(words: list[str]) -> list[list[str]]: # Group words that use the same letters, the same number of times. # Groups in first-seen order; words keep their order in a group. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']) → [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
2. ○Not run yet: group_anagrams(['aab', 'abb']) → [['aab'], ['abb']]
3. ○Not run yet: group_anagrams(['ab', 'ba', 'ab']) → [['ab', 'ba', 'ab']]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: 20,000 words of 24 letters, no two in the same group → 20000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

group_anagrams()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: search a list of keys	O(n² · k)	O(n · k)	Needs no hashing at all	Far too slow for many groups	Only a handful of words
Better: tuple of sorted letters	O(n · k log k)	O(n · k)	Short, clear, fast for everyday words	Sorts every word	Almost always
Best: tuple of letter counts	O(n · k)	O(n · k)	No sort, so it scales with long words	Slower for short words in Python; a key per word is always 26 numbers	Words are long, or the interviewer asks for O(n · k)

How much work is that? Each bar is one rung at the same number of words, when no two words share a group. Better and Best both do one dict lookup per word; they differ in how they build each key.

Group anagrams: key checks at n words

1. OkaySearch a list of keys · O(n²)≈ 5,000,000,000 key checks

2. BetterTuple of sorted letters · O(n)≈ 100,000 dict lookups

3. BestTuple of letter counts · O(n)≈ 100,000 dict lookups

At n = 100,000, Okay does about 50,000 times more work than Better.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Common mistakes and edge cases

!+= on a list inside a tuple

With t = ([1], 2), the line t[0] += [3] raises TypeError: 'tuple' object does not support item assignment. Yet t is now ([1, 3], 2). The list’s += ran in place first; only putting it back into the tuple failed. Use t[0].append(3) or t[0].extend([3]), which never try to change the tuple.

• A tuple holding a list can’t be a key: {(1, [2]): 0} raises unhashable type: 'list'. Every item, at every level, must be unable to change. Practice 3 is about this.
• A set of letters forgets how many: frozenset("aab") == frozenset("abb") is True. A frozenset is a set that can’t change, so it can be a key, but here it would put aab and abb in one group.
• += versus +: on a list, a += [x] changes the list in place, so other names see it. a = a + [x] makes a new list and moves only a.
• Text methods return new text: name.strip() on its own line does nothing you can see. Write name = name.strip().
• A function can change your list, never your text: a function that does items.append(1) changes the caller’s list. One that does text += "!" only moves its own name.
• Building text in a loop: each s += piece makes new text. To join many pieces, collect them in a list and call "".join(parts) once.

Say it in the interview

Questions to ask first

• Are the words only lowercase a to z? Could there be capitals, spaces or other letters?
• Should groups and the words in them keep their first-seen order?
• How long are the words? That decides between sorting and counting.

A 60-second walkthrough

“Anagrams have the same letters, so I need a key that’s the same for every word in a group. Sorting the letters works, but a sorted list can’t be a dict key: lists can change, and a dict needs keys whose hash never changes. So I freeze it into a tuple, tuple(sorted(word)), and group words in a dict of lists. That’s O(n · k log k). To drop the sort, I can count the 26 letters into a list and use tuple(counts) as the key, which is O(n · k).”

Likely follow-ups

• Why can’t a list be a dict key? A dict finds keys by their hash, which comes from the value. A list can change, so its hash would become wrong. Python refuses to hash it.
• Which built-in types can change? list, dict, set and bytearray. int, float, bool, str, tuple, frozenset, bytes and None can’t.
• Can a tuple always be a key? Only if everything inside it can be hashed. (1, [2]) can’t.
• What happens with letters outside a to z? The counts version needs a bigger table or a dict of counts. The sorted version works for any text.

Practice

Three problems, from easy to hard. Each has hints, tests you can run here, and its own Okay, Better and Best answers. Try before you open them.

1. Count the distinct points (easy)

points is a list of [x, y] pairs of whole numbers. Return how many different points there are. Two points are the same only if both numbers match, so [1, 2] and [2, 1] are different. Leave points as it was.

Example: count_distinct([[1, 2], [3, 4], [1, 2], [2, 1]]) gives 3.

Hint 1 of 3

A set keeps each value once. Can [1, 2] go in a set?

Hint 2 of 3

A list can’t go in a set, but a tuple can: (1, 2).

Hint 3 of 3

If you sort to put equal points side by side, use sorted(points), not points.sort(), which changes the caller’s list.

Count the distinct points

Ctrl + Enter runs

def count_distinct(points: list[list[int]]) -> int: # How many different [x, y] points? Leave points unchanged. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: count_distinct([[1, 2], [3, 4], [1, 2], [2, 1]]) → 3
2. ○Not run yet: count_distinct([[-1, 5], [-1, 5], [-1, 5]]) → 1
3. ○Not run yet: Extra test
4. ○Not run yet: Extra test
5. ○Not run yet: Speed test: 30,000 points, all different → 30000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

count_distinct()Run onceVisualize

Show the Okay, Better and Best answers

Okay

A list of points seen

The idea: Keep a list of the points seen so far, and add each point that isn’t in it yet.

point not in seen compares lists with ==, which works for lists. But it checks them one by one.

def count_distinct(points: list[list[int]]) -> int:
    """Count the different points. Keep a list of the ones seen and search it."""
    seen: list[list[int]] = []
    for point in points:
        if point not in seen:
            seen.append(point)
    return len(seen)

Time

O(n²)

Space

O(n)

Why

Each point may be compared with every point seen so far.

Where it breaks: 30,000 different points need about 450 million checks. It fails the speed test.

Better

Sort a copy, then count the changes

The idea: Sort a new list of the points, so equal points sit side by side, and count each point unlike the one before it.

The waste in Okay: it compares each point with every other one.

Lists can be sorted: Python compares them item by item. sorted(points) makes a new list, so the caller’s points keeps its order. points.sort() would sort the caller’s own list, and the hidden test would catch it.

Highlighted lines are new in this rung.

def count_distinct(points: list[list[int]]) -> int:
    """Count the different points: sort a copy, then count each point unlike the one before."""
    ordered = sorted(points)  # a new list; points stays as it was
    count = 0
    for i, point in enumerate(ordered):
        if i == 0 or point != ordered[i - 1]:
            count += 1
    return count

Time

O(n log n)was O(n²)

Space

O(n)

Why

The sort does the work; the count is one pass.

What changed from the previous rung

def count_distinct(points: list[list[int]]) -> int:
    """Count the different points. Keep a list of the ones seen and search it."""
    seen: list[list[int]] = []
    for point in points:
        if point not in seen:
            seen.append(point)
    return len(seen)
    """Count the different points: sort a copy, then count each point unlike the one before."""
    ordered = sorted(points)  # a new list; points stays as it was
    count = 0
    for i, point in enumerate(ordered):
        if i == 0 or point != ordered[i - 1]:
            count += 1
    return count

Where it breaks: the sort costs O(n log n), more than one pass.

Best

A set of tuples

The idea: Put each point in a set as a tuple, (x, y), then count the set.

The waste in Better: it puts all the points in order, when it only needs to know which are equal.

[x, y] can’t go in a set, because a list can change. (x, y) can.

Highlighted lines are new in this rung.

def count_distinct(points: list[list[int]]) -> int:
    """Count the different points: put each one in a set, as a tuple."""
    seen: set[tuple[int, int]] = set()
    for x, y in points:
        seen.add((x, y))  # [x, y] can't go in a set, (x, y) can
    return len(seen)

Time

O(n)was O(n log n)

Space

O(n)

Why

Each point is added to the set in one step.

What changed from the previous rung

def count_distinct(points: list[list[int]]) -> int:
    """Count the different points: sort a copy, then count each point unlike the one before."""
    ordered = sorted(points)  # a new list; points stays as it was
    count = 0
    for i, point in enumerate(ordered):
        if i == 0 or point != ordered[i - 1]:
            count += 1
    return count
    """Count the different points: put each one in a set, as a tuple."""
    seen: set[tuple[int, int]] = set()
    for x, y in points:
        seen.add((x, y))  # [x, y] can't go in a set, (x, y) can
    return len(seen)

When Best isn’t best: with only a few points, the list in Okay is fine and needs nothing new. And if you also need the points in order, Better gives you that at no extra cost.

2. When does the playlist repeat? (medium)

A playlist starts empty. Each edit is "+song", which adds the song at the end, or "-song", which removes the first copy of that song (it’s always there). Return the number of the first edit, counting from 1, after which the playlist is exactly as it was at some earlier moment. The empty start counts. Exactly means the same songs in the same order. Return -1 if it never happens. Song names are never empty, and may hold any characters.

Example: first_repeat(["+a", "+b", "-b"]) gives 3: after edit 3 the playlist is ["a"] again. first_repeat(["+a", "+b", "-a", "+a"]) gives -1, because ["b", "a"] isn’t ["a", "b"].

Hint 1 of 3

Keep every version you’ve seen. If you store playlist itself, every stored version is the same list, which keeps changing.

Hint 2 of 3

A set finds a version in one step, but a list can’t go in a set.

Hint 3 of 3

tuple(playlist) is a snapshot that can’t change. Joining the songs into text looks similar, but can two different playlists give the same text?

When does the playlist repeat?

Ctrl + Enter runs

def first_repeat(edits: list[str]) -> int: # The number of the first edit after which the playlist is one it # has been before (the empty start counts), or -1. return -1

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: first_repeat(['+a', '+b', '-b']) → 3
2. ○Not run yet: first_repeat(['+a', '-a']) → 2
3. ○Not run yet: first_repeat(['+a', '+b', '-a', '+a']) → -1
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: 39,999 edits, and no version repeats → -1

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

first_repeat()Run onceVisualize

Show the Okay, Better and Best answers

Okay

A list of copies

The idea: After each edit, look for the playlist in a list of copies of every earlier version, then add a copy.

The copy matters. versions.append(playlist) would store the same list each time, and that one list keeps changing. Then playlist in versions soon finds the list itself, and reports a repeat that never happened.

def first_repeat(edits: list[str]) -> int:
    """The first edit after which the playlist is one it has been before, or -1.

    Keep a copy of every version in a list, and search it.
    """
    playlist: list[str] = []
    versions = [playlist.copy()]  # the empty start counts
    for step, edit in enumerate(edits, start=1):
        song = edit[1:]
        if edit[0] == "+":
            playlist.append(song)
        else:
            playlist.remove(song)
        if playlist in versions:
            return step
        versions.append(playlist.copy())  # a copy: playlist keeps changing
    return -1

Time

O(e² · s)

Space

O(e · s)

Why

e edits, each compared with every earlier version of up to s songs.

Where it breaks: speed. With 39,999 edits and no repeat, it makes about 800 million comparisons.

Better

A set of texts

The idea: Join each version into text, like 'a,b', and keep the texts in a set.

The waste in Okay: it compares the playlist with every earlier version, one by one.

Text can’t change, so it can go in a set. It’s also a fresh object each time, so nothing needs copying.

Highlighted lines are new in this rung.

def first_repeat(edits: list[str]) -> int:
    """The first edit after which the playlist is one it has been before, or -1.

    Turn each version into text, and keep the texts in a set.
    """
    playlist: list[str] = []
    seen = {""}  # the empty start, as text
    for step, edit in enumerate(edits, start=1):
        song = edit[1:]
        if edit[0] == "+":
            playlist.append(song)
        else:
            playlist.remove(song)
        text = ",".join(playlist)
        if text in seen:
            return step
        seen.add(text)
    return -1

Time

O(e · s)was O(e² · s)

Space

O(e · s)

Why

Each version is joined once and found in the set in one step.

What changed from the previous rung

def first_repeat(edits: list[str]) -> int:
    """The first edit after which the playlist is one it has been before, or -1.

    Keep a copy of every version in a list, and search it.
    Turn each version into text, and keep the texts in a set.
    """
    playlist: list[str] = []
    versions = [playlist.copy()]  # the empty start counts
    seen = {""}  # the empty start, as text
    for step, edit in enumerate(edits, start=1):
        song = edit[1:]
        if edit[0] == "+":
            playlist.append(song)
        else:
            playlist.remove(song)
        if playlist in versions:
        text = ",".join(playlist)
        if text in seen:
            return step
        versions.append(playlist.copy())  # a copy: playlist keeps changing
        seen.add(text)
    return -1

Where it breaks: a song with a comma in its name. ["a,b"] and ["a", "b"] both join to "a,b", so Better sees a repeat that isn’t there. In the hidden test it answers 6 instead of -1.

Best

A set of tuples

The idea: Freeze each version with tuple(playlist), and keep the tuples in a set.

The waste in Better: it turns songs into text and loses where one song ends and the next begins.

A tuple keeps each song as its own item, so two playlists give equal tuples only when they really are the same. And a tuple can’t change, so the stored version stays as it was while playlist keeps changing.

Highlighted lines are new in this rung.

def first_repeat(edits: list[str]) -> int:
    """The first edit after which the playlist is one it has been before, or -1.

    Freeze each version into a tuple, and keep the tuples in a set.
    """
    playlist: list[str] = []
    seen: set[tuple[str, ...]] = {()}  # the empty start
    for step, edit in enumerate(edits, start=1):
        song = edit[1:]
        if edit[0] == "+":
            playlist.append(song)
        else:
            playlist.remove(song)
        version = tuple(playlist)  # can't change, so the set can keep it
        if version in seen:
            return step
        seen.add(version)
    return -1

Time

O(e · s)

Space

O(e · s)

Why

The same work as Better, without the mix-ups.

What changed from the previous rung

def first_repeat(edits: list[str]) -> int:
    """The first edit after which the playlist is one it has been before, or -1.

    Turn each version into text, and keep the texts in a set.
    Freeze each version into a tuple, and keep the tuples in a set.
    """
    playlist: list[str] = []
    seen = {""}  # the empty start, as text
    seen: set[tuple[str, ...]] = {()}  # the empty start
    for step, edit in enumerate(edits, start=1):
        song = edit[1:]
        if edit[0] == "+":
            playlist.append(song)
        else:
            playlist.remove(song)
        text = ",".join(playlist)
        if text in seen:
        version = tuple(playlist)  # can't change, so the set can keep it
        if version in seen:
            return step
        seen.add(text)
        seen.add(version)
    return -1

When Best isn’t best: each version costs a tuple as long as the playlist. For long playlists and many edits, store a short fingerprint of each version instead, and check for real when two fingerprints match.

3. Remove duplicate records (hard)

records is a list of records from an API. Each is a dict, a list, text, a whole number, True, False or None, and dicts and lists can be nested to any depth. Return the records in order, without any record that is equal (==) to an earlier one. Dicts are equal when they have the same keys and values, in any order. Leave records as it was.

Example: with records = [{"id": 1, "tags": ["a"]}, {"tags": ["a"], "id": 1}, {"id": 1, "tags": ["b"]}], dedupe(records) gives the first and the third.

Hint 1 of 3

A set would make this fast, but dicts and lists can’t go in one.

Hint 2 of 3

Turn each record into an equal value that can’t change: a list into a tuple, a dict into a frozenset of its (key, value) pairs.

Hint 3 of 3

A tuple holding a list still can’t go in a set. Freeze every level: let your freeze function call itself on each item.

Remove duplicate records

Ctrl + Enter runs

def dedupe(records: list) -> list: # Keep each record unless it equals (==) an earlier one, in order. return records

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: dedupe([{'id': 1, 'tags': ['a']}, {'tags': ['a'], 'id': 1}, {'id': 1, 'tags': ['b']}]) → [{'id': 1, 'tags': ['a']}, {'id': 1, 'tags': ['b']}]
2. ○Not run yet: dedupe([[1, 2], [2, 1], [1, 2]]) → [[1, 2], [2, 1]]
3. ○Not run yet: dedupe([{'id': 1, 'n': 'x'}, {'n': 'x', 'id': 1}]) → [{'id': 1, 'n': 'x'}]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Extra test
8. ○Not run yet: Extra test
9. ○Not run yet: Speed test: 25,000 records, all different → 25000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

dedupe()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Search what you kept

The idea: Keep each record that isn’t already in the kept list, compared with ==.

== already knows that dicts with the same keys and values are equal, in any order, at any depth. So this is right.

def dedupe(records: list) -> list:
    """Keep the first of each group of equal records, in order. Search what's kept."""
    kept: list = []
    for record in records:
        if record not in kept:
            kept.append(record)
    return kept

Time

O(n² · r)

Space

O(n)

Why

Each record may be compared with every kept record, each of size up to r.

Where it breaks: speed. 25,000 different records need about 300 million comparisons.

Better

Freeze the top level

The idea: Turn a list into a tuple and a dict into a frozenset of its pairs, then keep a set of those.

The waste in Okay: it compares each record with all the others, one by one.

A frozenset is a set that can’t change. Its pairs have no order, so {"id": 1, "n": "x"} and {"n": "x", "id": 1} freeze to equal values. Flat records pass.

Highlighted lines are new in this rung.

def freeze(value: object) -> object:
    """Freeze the top level only: a list becomes a tuple, a dict a frozenset of its pairs."""
    if isinstance(value, list):
        return tuple(value)
    if isinstance(value, dict):
        return frozenset(value.items())
    return value


def dedupe(records: list) -> list:
    """Keep the first of each group of equal records, in order. Use a set of frozen records."""
    seen: set = set()
    kept: list = []
    for record in records:
        key = freeze(record)
        if key not in seen:
            seen.add(key)
            kept.append(record)
    return kept

Time

O(n · r)was O(n² · r)

Space

O(n · r)

Why

Each record is frozen once and found in the set in one step.

What changed from the previous rung

def freeze(value: object) -> object:
    """Freeze the top level only: a list becomes a tuple, a dict a frozenset of its pairs."""
    if isinstance(value, list):
        return tuple(value)
    if isinstance(value, dict):
        return frozenset(value.items())
    return value


def dedupe(records: list) -> list:
    """Keep the first of each group of equal records, in order. Search what's kept."""
    """Keep the first of each group of equal records, in order. Use a set of frozen records."""
    seen: set = set()
    kept: list = []
    for record in records:
        if record not in kept:
        key = freeze(record)
        if key not in seen:
            seen.add(key)
            kept.append(record)
    return kept

Where it breaks: a list or dict inside a record. tuple([1, [2]]) is (1, [2]), a tuple holding a list, and the set raises TypeError: unhashable type: 'list'. The first test fails this way.

Best

Freeze every level

The idea: freeze calls itself on every item, so lists become tuples and dicts become frozensets all the way down.

The waste in Better: it stops one level down, where the lists and dicts are still the kind that can change.

Two records freeze to equal values exactly when they are equal. A tuple never equals a frozenset, so [] and {} stay apart, as they should.

Highlighted lines are new in this rung.

def freeze(value: object) -> object:
    """An equal value that can't change at any depth, so a set can hold it."""
    if isinstance(value, list):
        return tuple(freeze(item) for item in value)
    if isinstance(value, dict):
        return frozenset((key, freeze(item)) for key, item in value.items())
    return value  # text, numbers, True, False and None can't change already


def dedupe(records: list) -> list:
    """Keep the first of each group of equal records, in order. Use a set of frozen records."""
    seen: set = set()
    kept: list = []
    for record in records:
        key = freeze(record)
        if key not in seen:
            seen.add(key)
            kept.append(record)
    return kept

Time

O(n · r)

Space

O(n · r)

Why

Every part of every record is frozen once.

What changed from the previous rung

def freeze(value: object) -> object:
    """Freeze the top level only: a list becomes a tuple, a dict a frozenset of its pairs."""
    """An equal value that can't change at any depth, so a set can hold it."""
    if isinstance(value, list):
        return tuple(value)
        return tuple(freeze(item) for item in value)
    if isinstance(value, dict):
        return frozenset(value.items())
    return value
        return frozenset((key, freeze(item)) for key, item in value.items())
    return value  # text, numbers, True, False and None can't change already


def dedupe(records: list) -> list:
    """Keep the first of each group of equal records, in order. Use a set of frozen records."""
    seen: set = set()
    kept: list = []
    for record in records:
        key = freeze(record)
        if key not in seen:
            seen.add(key)
            kept.append(record)
    return kept

When Best isn’t best: for records from a known schema, a key of just the fields that matter, like (record["id"], record["version"]), is faster and says what “the same” means. And for data that’s already JSON text, comparing the text is risky: the same dict can be written with its keys in a different order.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputWhat does this print?

   a = [1]
   b = a
   a += [2]
   s = "hi"
   t = s
   s += "!"
   print(b, t)

   [1] hi[1, 2] hi![1] hi![1, 2] hi

   Check answer
2. Multiple choiceWhich of these can be a dict key?

   (1, 2)[1, 2](1, [2]){1, 2}

   Check answer
3. Spot the bugThis should tidy every name in the list. Why does names stay the same?

   names = [" ana", "bo "]
   for name in names:
       name.strip()
   print(names)

   strip() only works on one name at a timeThe loop needs range(len(names))Text can’t change: strip() gives back new text, and this code throws it awayprint() shows the list from before the loop

   Check answer
4. Predict the outputWhat is t after this code?

   t = ([1], 2)
   try:
       t[0] += [3]
   except TypeError:
       pass

   ([1], 2)([1, 3], 2)([3], 2)It stops with an error, so t is gone

   Check answer
5. Pick the patternYou need to count the different [x, y] points in a big list. What do you put in the set?

   Each [x, y] list as it isEach point as a tuple, (x, y)Each point as frozenset([x, y])str(x + y)

   Check answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1Which built-in types can change in place?Show answer
• Card 2Why can’t a list be a dict key?Show answer
• Card 3Can a tuple always be a dict key?Show answer
• Card 4What does s.upper() do to s?Show answer
• Card 5a += [x] versus a = a + [x], on a list?Show answer
• Card 6How do you turn nested lists and dicts into a key?Show answer

Add 6 cards to my review deck

Cheat sheet

• Can change: list, dict, set. Can’t: numbers, str, tuple, frozenset, None.
• A change to a list shows through every name for it. A “change” to text makes new text.
• Of the built-in types, only ones that can’t change can be dict keys or set items. A tuple counts only if all its items can’t change.
• Make a list into a key with tuple(items), and a set with frozenset(items). Freeze every level for nested data.
• a += [x] changes a list in place. a = a + [x] makes a new one. s.upper() gives back new text.

Go deeper

• Objects, values and types, from the Python reference: what mutable and immutable mean.
• Hashable, in the Python glossary.
• From the Python FAQ: Why must dictionary keys be immutable? and Why does a_tuple[i] += ['item'] raise an exception when the addition works?
• Draw your own: the memory diagram on the Python visualizer.
• Next on the Python roadmap: Functions, *args, **kwargs and the mutable-default trap.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Say which built-in types can change in place and which can’t
• Predict what +=, = and methods do to a list, to text and to a tuple, and which names see it
• Explain why only objects that can’t change can be dict keys or set items
• Turn a list into a key with tuple(), at every level when you need to

✓Mark as completeI already know this

Status: Not started