My anagram check says aab and abb match

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapLists and strings in two minutes· 2 min

A list keeps its items in a row, from index 0, so a[i] is one step. But finding a value in a list, x in a, compares it with the items one by one: O(n). A string is a row of characters that can’t be changed, and s.count(c) reads all of s. The full lesson: I reversed the list, but the caller’s list didn’t change.

Quick recapDicts in two minutes· 2 min

A dict maps keys to values. d[key] gives the value, and raises KeyError if the key isn’t there. d.get(key, 0) gives 0 instead. key in d checks the keys.

ages = {'ann': 31}
ages['bo'] = 27        # add a key, or change its value
ages['ann']            # 31
ages.get('cy', 0)      # 0: no KeyError
'bo' in ages           # True
len(ages)              # 2

See the problem

The interview task: two words are anagrams if one uses exactly the letters of the other, each the same number of times, like “listen” and “silent”. You think: same letters, so compare the sets.

def is_anagram(a, b):
    return set(a) == set(b)

is_anagram('listen', 'silent') gives True. Then the interviewer tries is_anagram('aab', 'abb'), and it gives True too. But “aab” has two a’s, and “abb” has one.

A set keeps one of each item, so set('aab') and set('abb') are both {'a', 'b'}. It knows which letters there are, and forgets how many. To compare words, you need each letter and its count: a dict from letter to count.

Define the task

Write is_anagram(a, b).

• Input: two strings, a and b. Every character counts, including spaces and capitals. Up to 200,000 characters each.
• Output: True if b has exactly the characters of a, each the same number of times, else False.
• The hard part: it must be fast for 200,000 characters, and light on memory: one test allows 1 MB.

Example: is_anagram('listen', 'silent') gives True. is_anagram('aab', 'abb') gives False.

Pause and think

⏸ Pause and think

Before you write any code: what would you need to write down, on paper, to check two long words are anagrams in one read of each?

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

Hints open one at a time:

Hint 1 of 3

Read a once and keep a count of each letter.

Hint 2 of 3

Then read b, take one off that letter’s count for each letter. What does it mean if a count goes below zero?

Hint 3 of 3

A dict holds the counts: letter → count. Each update is about one step, however many letters there are.

Understand the idea

A dict finds a key in about one step. It keeps a table of slots, like a set. To store a key, Python works out a whole number from the key, its hash, and uses it to pick a slot. To find the key again, it works out the same slot and looks there, without looking through the other keys. A dict is a set with a value kept next to each key. Where a set looks shows the slots, step by step.

Clashes keep it from being a promise. Two keys can pick the same slot, so Python tries another slot, and another. It keeps the table partly empty, and moves to a bigger one when it fills up. So a look almost always takes one slot or a few. That’s O(1) on average. If many keys clashed, a look could take O(n).

Keys must be hashable. A key’s hash must never change, or the dict would look in the wrong slot. So strings, numbers, and tuples of those can be keys. Lists, dicts and sets can’t: they can change, and so can a tuple that holds one, so (1, [2]) can’t be a key either. Python says my list can’t be a dict key shows why. To use a list as a key, make it a tuple.

Now watch what happens without a dict. Okay counts each letter by reading both words again with count(), and the panel counts the letters read. Try your own words, up to 7 letters each.

Count each letter by reading both words

⤢ Full view

1. l0
2. i1
3. s2
4. t3
5. e4
6. n5

Work so far

letters read	0

Step 1 of 8. Both words have 6 letters. Now count each letter of word a, in both words. Question: With 6 letters in each word, how many letters can the counts read, at most?

What happens next? With 6 letters in each word, how many letters can the counts read, at most?

123672Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def is_anagram(a: str, b: str) -> bool:
2    if len(a) != len(b):
3        return False
4    # Each count() reads the whole word, once for every letter of a.
5    return all(a.count(c) == b.count(c) for c in a)

Try your own input

Word aWord bShow it

The tools you’ll use most:

from collections import Counter, defaultdict

counts = {}
for c in 'aab':
    counts[c] = counts.get(c, 0) + 1    # {'a': 2, 'b': 1}

Counter('aab')                          # the same counts, in one call
Counter('aab') == Counter('aba')        # True: compares every count

groups = defaultdict(list)              # a missing key starts as []
for word in ['tea', 'eat', 'tan']:
    groups[''.join(sorted(word))].append(word)
# {'aet': ['tea', 'eat'], 'ant': ['tan']}

Four patterns. Most hash map answers are one of these:

• Count: how many of each thing. Counter, or d[x] = d.get(x, 0) + 1.
• Seen: have I met this before? A set, as in the Big-O lesson’s duplicate check.
• Index: where did I see this value? seen[value] = i, as in Two Sum.
• Group: which things share a key? defaultdict(list), with a key made from each thing.

What each dict step costs, for a dict of n keys:

Step	Cost
d[k], d.get(k), k in d	O(1) on average
d[k] = v, del d[k]	O(1) on average
len(d)	O(1)
for k in d, d.items()	O(n)
Counter(s) for a string of length n	O(n)
d1 == d2	O(n)
k in d.values()	O(n): values aren’t looked up by slot

Climb the ladder

All three give True for “listen” and “silent”, and False for “aab” and “abb”. What changes is the time and the memory.

Okay

Count each letter in both words

The idea: For each letter of a, count it in a and in b with count(). Every count must match.

Right, short, and it keeps nothing extra. It even checks the length first, which a set can’t do for you.

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    # Each count() reads the whole word, once for every letter of a.
    return all(a.count(c) == b.count(c) for c in a)

Time

O(n²)

Space

O(1)

Why

n letters, each with two count() calls that read n letters: 2n² in all, when the words are anagrams.

Where it breaks: speed. count() keeps nothing between calls, so a letter that comes 1,000 times is counted 1,000 times. Two words of 200,000 letters take about 80 billion letter reads: it runs out of time.

Better

Sort both words, then compare

The idea: Two anagrams sort into the same list of letters.

The waste in Okay: it reads both words again for every letter. Sorted, every a comes first, then every b, so one pass compares all the counts at once.

Highlighted lines are new in this rung.

def is_anagram(a: str, b: str) -> bool:
    # The same letters, the same number of times, sort into the same list.
    return sorted(a) == sorted(b)

Time

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

Space

O(n)was O(1)

Why

Two sorts of n letters, then one pass to compare. sorted() makes a new list of n letters for each word.

What changed from the previous rung

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    # Each count() reads the whole word, once for every letter of a.
    return all(a.count(c) == b.count(c) for c in a)
    # The same letters, the same number of times, sort into the same list.
    return sorted(a) == sorted(b)

Where it breaks: memory. sorted() makes a list with a pointer for every letter, one for each word: megabytes for 200,000 letters, when there are only 26 different ones to count.

Best

One dict of counts

The idea: Add 1 for each letter of a, then take 1 away for each letter of b. A count below 0 means b has too many of it.

The waste in Better: it puts every letter in order, when all it needs is how many of each. A dict keeps one number per different letter, and each update is about one step.

Why is it enough to check for below 0? The words are the same length, so if b never takes more of a letter than a put in, every count ends at exactly 0.

One dict of counts

⤢ Full view

1. l0
2. i1
3. s2
4. t3
5. e4
6. n5

counts

empty

Step 1 of 14. Start with an empty dict, counts: letter → how many. Question: With 6 letters in each word, about how many dict steps will it take, at most?

What happens next? With 6 letters in each word, about how many dict steps will it take, at most?

123672Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def is_anagram(a: str, b: str) -> bool:
2    if len(a) != len(b):
3        return False
4    counts: dict[str, int] = {}
5    for c in a:
6        counts[c] = counts.get(c, 0) + 1
7    for c in b:
8        counts[c] = counts.get(c, 0) - 1
9        if counts[c] < 0:  # b has more of c than a has
10            return False
11    return True

Try your own input

Word aWord bShow it

Highlighted lines are new in this rung.

def is_anagram(a: str, b: str) -> bool:
    if len(a) != len(b):
        return False
    counts: dict[str, int] = {}
    for c in a:
        counts[c] = counts.get(c, 0) + 1
    for c in b:
        counts[c] = counts.get(c, 0) - 1
        if counts[c] < 0:  # b has more of c than a has
            return False
    return True

Time

O(n) on averagewas O(n log n)

Space

O(k)was O(n)

Why

One dict step for each letter of each word. The dict holds one count for each of the k different letters, and k is at most n.

What changed from the previous rung

def is_anagram(a: str, b: str) -> bool:
    # The same letters, the same number of times, sort into the same list.
    return sorted(a) == sorted(b)
    if len(a) != len(b):
        return False
    counts: dict[str, int] = {}
    for c in a:
        counts[c] = counts.get(c, 0) + 1
    for c in b:
        counts[c] = counts.get(c, 0) - 1
        if counts[c] < 0:  # b has more of c than a has
            return False
    return True

When Best isn’t best: in real code, Counter(a) == Counter(b) says the same in one line, and its counting loop runs in C, so it’s faster too. If the words are only a to z, a list of 26 counts, counts[ord(c) - ord('a')], does the same without hashing. And for short words, sorted(a) == sorted(b) is clear and quick enough.

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 runs out of time on the speed test. Better fails the 1 MB test.

Check two words are anagrams

Ctrl + Enter runs

def is_anagram(a: str, b: str) -> bool: # True if b has exactly the characters of a, # each the same number of times. return False

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

1. ○Not run yet: is_anagram('listen', 'silent') → True
2. ○Not run yet: is_anagram('aab', 'abb') → False
3. ○Not run yet: is_anagram('rat', 'car') → False
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: two words of 200,000 letters → True
7. ○Not run yet: Two words of 200,000 letters, in 1 MB → True

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

Try your own input

Arguments, separated by commas as in Python

is_anagram()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: count each letter in both words	O(n²)	O(1)	Short, and keeps nothing	Too slow past about 50,000 letters	The words are short
Better: sort both, then compare	O(n log n)	O(n)	One line, easy to trust, and quick: the sort runs in C	A sorted copy of each word	Memory isn’t tight
Best: one dict of counts	O(n) on average	O(k), k different letters	Little memory, and stops at the first letter b has too many of	A few more lines, and its Python loop is slower than sorted()	Almost always, or Counter(a) == Counter(b)

How much work is that? Each bar is one rung, with two words of n letters. Pick a size, or run the race.

Anagrams: steps with two words of n letters

1. OkayCount each letter in both words · O(n²)≈ 20,000,000,000 letters read

2. BetterSort both, then compare · O(n log n)≈ 1,700,000 sort steps

3. BestOne dict of counts · O(n) on average≈ 200,000 dict steps

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

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.

The race counts steps and gives each one the same time, but real steps differ. sorted() runs in C, so with two words of 200,000 letters Better takes about 30 ms, where Best’s Python loop takes about 200 ms. Counter(a) == Counter(b) counts in C too: about 15 ms. Best’s loop wins on memory, not speed.

Common mistakes and edge cases

!A set forgets how many

set(a) == set(b) checks which items there are, not how many of each. For anagrams, counts, or anything where repeats matter, use a dict or Counter.

• d[k] raises KeyError for a missing key. Use d.get(k, 0), k in d first, or a defaultdict.
• A defaultdict adds keys when you read them. groups['zz'] on a defaultdict(list) adds 'zz': [], even if you only meant to look. Use 'zz' in groups to check.
• Don’t add or remove keys while looping over a dict. Python raises RuntimeError: dictionary changed size during iteration. Loop over list(d) instead.
• Lists can’t be keys. d[[1, 2]] = 'x' raises TypeError: unhashable type: 'list'. Use the tuple (1, 2).
• Case and accents are different characters. 'Tea' and 'eat' aren’t anagrams unless you lower-case first. And “é” can be one character or two (e plus an accent), so normalize text from users with unicodedata.normalize('NFC', s).
• O(1) is an average. Keys whose hashes clash share a slot. Python’s string hashes are random per run, so an attacker can’t easily pick clashing keys. But a bad custom __hash__ can make every look O(n).

Say it in the interview

Questions to ask first

• Do case, spaces and punctuation count?
• Only a to z, or any Unicode text?
• How long can the words be? Is memory tight?

A 60-second walkthrough

“A set would lose the counts, so aab and abb would match. Sorting both words and comparing works, in O(n log n) time, but it copies both words. Instead I’ll count with a dict: if the lengths differ, return False. Then add 1 for each letter of a, and take 1 away for each letter of b. If a count goes below zero, b has a letter a doesn’t have enough of, so return False. If it never does, every count ends at zero, so return True. Each dict step is O(1) on average, so that’s O(n) time, and O(k) space for k different letters. In real code I’d write Counter(a) == Counter(b).”

Likely follow-ups

• What if it’s only lowercase a to z? A list of 26 counts: no hashing, and O(1) memory, since it’s always 26.
• Group a list of words into anagrams? A defaultdict(list) keyed by each word’s sorted letters, or by a tuple of its 26 counts.
• Why is a dict lookup only O(1) on average? Keys can clash on a slot. Python keeps the table partly empty, so clashes are rare, but in the worst case one look checks every key.
• Why can’t a list be a key? Its hash would change when the list changes, and the dict would look in the wrong slot. A tuple can’t change, so it can be a key, as long as everything in it could be a key too.

Practice

Three problems, from easy to medium. Each uses a dict or a set, and each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. Cut a note from a magazine (easy)

Write can_write(note, magazine): True if you can make note by cutting characters out of magazine, using each character of the magazine at most once. Spaces count as characters.

Example: can_write('cab', 'abcd') gives True. can_write('aa', 'ab') gives False: the magazine has only one a.

Hint 1 of 3

A list of the magazine’s characters, removing each one you use, works. But each remove searches and shifts the list: O(n) each time.

Hint 2 of 3

Sorting both and walking them side by side is O(n log n). But the sorted magazine is a full copy.

Hint 3 of 3

Count the magazine’s characters in a dict once. Then, for each character of the note, take one away. Out of one? Then it can’t be done.

Cut a note from a magazine

Ctrl + Enter runs

def can_write(note: str, magazine: str) -> bool: # Can note be cut out of magazine, using # each character of it at most once? return False

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

1. ○Not run yet: can_write('cab', 'abcd') → True
2. ○Not run yet: can_write('aa', 'ab') → False
3. ○Not run yet: can_write('', '') → True
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: a note of 150,000 b’s, from a magazine with 150,000 a’s before its b’s → True
7. ○Not run yet: A magazine of 400,000 characters, in 1 MB → True

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

Try your own input

Arguments, separated by commas as in Python

can_write()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Cross off each character in a list

The idea: Make a list of the magazine’s characters. For each character of the note, remove it from the list, if it’s there.

It does what you’d do with scissors.

def can_write(note: str, magazine: str) -> bool:
    """Can note be cut out of magazine, using each letter of it at most once?"""
    letters = list(magazine)
    for c in note:
        if c not in letters:  # looks through the letters left, one by one
            return False
        letters.remove(c)
    return True

Time

O(n · m)

Space

O(m)

Why

For each of the note’s n characters, in and remove() look through and shift the magazine’s m characters.

Where it breaks: in and remove() look through the list from the front, one character at a time. When what the note needs is far along, as in the speed test, each of its 150,000 characters passes 150,000 others: billions of steps, and it runs out of time.

Better

Sort both, then walk them side by side

The idea: Sorted, the note’s characters can be matched in order against the magazine’s, skipping the ones the note doesn’t need.

The waste in Okay: it searches the magazine again for every character. Sorted, one walk does it.

Highlighted lines are new in this rung.

def can_write(note: str, magazine: str) -> bool:
    """Can note be cut out of magazine, using each letter of it at most once?"""
    need, have = sorted(note), sorted(magazine)
    j = 0
    for c in need:
        while j < len(have) and have[j] < c:
            j += 1
        if j == len(have) or have[j] != c:
            return False
        j += 1
    return True

Time

O((n + m) log(n + m))was O(n · m)

Space

O(n + m)

Why

Two sorts, then one walk over both. Each sorted list holds every character.

What changed from the previous rung

def can_write(note: str, magazine: str) -> bool:
    """Can note be cut out of magazine, using each letter of it at most once?"""
    letters = list(magazine)
    for c in note:
        if c not in letters:  # looks through the letters left, one by one
    need, have = sorted(note), sorted(magazine)
    j = 0
    for c in need:
        while j < len(have) and have[j] < c:
            j += 1
        if j == len(have) or have[j] != c:
            return False
        letters.remove(c)
        j += 1
    return True

Where it breaks: memory. The sorted magazine is a list of 400,000 pointers: megabytes, to write “hello”.

Best

Count the magazine, then spend the counts

The idea: A dict of how many of each character the magazine has. Each character of the note takes one away; none left means no.

The waste in Better: it puts every character in order, when only the counts matter. It’s the lesson’s anagram check, except the magazine may have extra.

Highlighted lines are new in this rung.

def can_write(note: str, magazine: str) -> bool:
    """Can note be cut out of magazine, using each letter of it at most once?"""
    have: dict[str, int] = {}
    for c in magazine:
        have[c] = have.get(c, 0) + 1
    for c in note:
        if have.get(c, 0) == 0:
            return False
        have[c] -= 1
    return True

Time

O(n + m) on averagewas O((n + m) log(n + m))

Space

O(k)was O(n + m)

Why

One dict step for each character of each string. The dict holds one count for each of the k different characters.

What changed from the previous rung

def can_write(note: str, magazine: str) -> bool:
    """Can note be cut out of magazine, using each letter of it at most once?"""
    need, have = sorted(note), sorted(magazine)
    j = 0
    for c in need:
        while j < len(have) and have[j] < c:
            j += 1
        if j == len(have) or have[j] != c:
    have: dict[str, int] = {}
    for c in magazine:
        have[c] = have.get(c, 0) + 1
    for c in note:
        if have.get(c, 0) == 0:
            return False
        j += 1
        have[c] -= 1
    return True

When Best isn’t best: not (Counter(note) - Counter(magazine)) says the same in one line: subtracting keeps only the counts the magazine can’t cover. It counts the whole note first, though, so it can’t stop early.

2. Words that follow a pattern (easy)

Write follows(pattern, words): True if each letter of pattern stands for one word, and each word for one letter, all the way through.

Example: follows('abba', ['dog', 'cat', 'cat', 'dog']) gives True. follows('abba', ['dog', 'dog', 'dog', 'dog']) gives False: a and b can’t both stand for dog.

Hint 1 of 3

Two places must have the same letter exactly when they have the same word. Checking every pair of places works, but it’s O(n²).

Hint 2 of 3

A dict from letter to word catches a letter that changes its word. Does it catch two letters sharing one word?

Hint 3 of 3

Keep a second dict, from word to letter, and check both ways at each place.

Words that follow a pattern

Ctrl + Enter runs

def follows(pattern: str, words: list[str]) -> bool: # Does each letter stand for one word, # and each word for one letter? return False

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

1. ○Not run yet: follows('abba', ['dog', 'cat', 'cat', 'dog']) → True
2. ○Not run yet: follows('abba', ['dog', 'cat', 'cat', 'fish']) → False
3. ○Not run yet: follows('aaaa', ['dog', 'cat', 'cat', 'dog']) → False
4. ○Not run yet: follows('abba', ['dog', 'dog', 'dog', 'dog']) → False
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: a pattern of 50,000 letters → True

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

Try your own input

Arguments, separated by commas as in Python

follows()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check every pair of places

The idea: For every two places, the letters must match exactly when the words match.

It’s the rule, word for word, and it checks both ways at once.

def follows(pattern: str, words: list[str]) -> bool:
    """Does each letter of pattern stand for one word, and each word for one letter?"""
    if len(pattern) != len(words):
        return False
    # Two places must have the same letter exactly when they have the same word.
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if (pattern[i] == pattern[j]) != (words[i] == words[j]):
                return False
    return True

Time

O(n²)

Space

O(1)

Why

n(n − 1)/2 pairs of places, each two comparisons.

Where it breaks: 50,000 places make about 1.25 billion pairs: it runs out of time.

Better

A dict from letter to word

The idea: Remember the word each letter first stood for. A letter with a different word later breaks the pattern.

The waste in Okay: it compares every pair of places, when each place only needs to agree with what its letter stood for before.

Highlighted lines are new in this rung.

def follows(pattern: str, words: list[str]) -> bool:
    """Does each letter of pattern stand for one word, and each word for one letter?"""
    if len(pattern) != len(words):
        return False
    word_for: dict[str, str] = {}
    for letter, word in zip(pattern, words, strict=True):
        if word_for.get(letter, word) != word:  # this letter stood for another word
            return False
        word_for[letter] = word
    return True

Time

O(n) on averagewas O(n²)

Space

O(k)

Why

One dict step for each place. The dict holds one word for each different letter.

What changed from the previous rung

def follows(pattern: str, words: list[str]) -> bool:
    """Does each letter of pattern stand for one word, and each word for one letter?"""
    if len(pattern) != len(words):
        return False
    # Two places must have the same letter exactly when they have the same word.
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if (pattern[i] == pattern[j]) != (words[i] == words[j]):
                return False
    word_for: dict[str, str] = {}
    for letter, word in zip(pattern, words, strict=True):
        if word_for.get(letter, word) != word:  # this letter stood for another word
            return False
        word_for[letter] = word
    return True

Where it breaks: it checks one way only. For 'abba' and four dogs, a stands for dog and b stands for dog too, and nothing objects. It says True.

Best

Two dicts, one each way

The idea: Remember the word for each letter and the letter for each word. Both must agree at every place.

The waste in Better: nothing, it’s a bug: a pattern is a match both ways, and it only checked one. The second dict catches two letters sharing a word.

Highlighted lines are new in this rung.

def follows(pattern: str, words: list[str]) -> bool:
    """Does each letter of pattern stand for one word, and each word for one letter?"""
    if len(pattern) != len(words):
        return False
    word_for: dict[str, str] = {}
    letter_for: dict[str, str] = {}
    for letter, word in zip(pattern, words, strict=True):
        if word_for.get(letter, word) != word or letter_for.get(word, letter) != letter:
            return False
        word_for[letter] = word
        letter_for[word] = letter
    return True

Time

O(n) on average

Space

O(k)

Why

Two dict steps for each place. Each dict holds one entry for each different letter or word.

What changed from the previous rung

def follows(pattern: str, words: list[str]) -> bool:
    """Does each letter of pattern stand for one word, and each word for one letter?"""
    if len(pattern) != len(words):
        return False
    word_for: dict[str, str] = {}
    letter_for: dict[str, str] = {}
    for letter, word in zip(pattern, words, strict=True):
        if word_for.get(letter, word) != word:  # this letter stood for another word
        if word_for.get(letter, word) != word or letter_for.get(word, letter) != letter:
            return False
        word_for[letter] = word
        letter_for[word] = letter
    return True

When Best isn’t best: len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words))) says the same in one line, when the lengths match: as many different pairs as different letters and different words means nothing is shared. It builds three sets and can’t stop early, so it’s less clear to explain.

3. The longest run of numbers in a row (medium)

Write longest_run(nums): the length of the longest run of whole numbers that follow on from each other, like 4, 5, 6, wherever they are in the list. Don’t change nums. There can be 100,000 numbers.

Example: longest_run([100, 4, 200, 1, 3, 2]) gives 4: 1, 2, 3 and 4.

Hint 1 of 3

For each number, count up while the next one is in the list. With x in a list, each check is O(n), and runs are counted again from every number in them.

Hint 2 of 3

Sorted, a run sits side by side. But sort() changes the caller’s list, and sorted() copies it.

Hint 3 of 3

Put the numbers in a set. Only start counting from a number whose x − 1 isn’t there: the start of a run. Each run is then counted once.

The longest run of numbers in a row

Ctrl + Enter runs

def longest_run(nums: list[int]) -> int: # The longest run like 4, 5, 6, in any order. # Don't change nums. return 0

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

1. ○Not run yet: longest_run([100, 4, 200, 1, 3, 2]) → 4
2. ○Not run yet: longest_run([]) → 0
3. ○Not run yet: longest_run([7]) → 1
4. ○Not run yet: Extra test
5. ○Not run yet: longest_run([3, 1, 2]), and nums must not change → 3
6. ○Not run yet: Speed test: 0 to 99,999, in mixed order → 100000

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

Try your own input

Arguments, separated by commas as in Python

longest_run()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Count up from every number

The idea: For each number x, count how many of x + 1, x + 2, … are in the list.

Clear, and it changes nothing.

def longest_run(nums: list[int]) -> int:
    """The length of the longest run of whole numbers in a row, like 4, 5, 6, in any order."""
    best = 0
    for x in nums:
        length = 1
        while x + length in nums:  # looks through the whole list
            length += 1
        best = max(best, length)
    return best

Time

O(n³)

Space

O(1)

Why

From each of n numbers, a run can be up to n long, and each step of it searches the list: O(n).

Where it breaks: 2,000 numbers in one run already take more than ten seconds. Each time the numbers double, it takes eight times as long, so 100,000 would take weeks.

Better

Sort, then walk the runs

The idea: Sorted, a run is side by side. Walk the list, growing the run while each number is one more than the last.

The waste in Okay: it searches the whole list for every next number, and counts each run again from every number in it. Sorted, one pass sees every run.

Highlighted lines are new in this rung.

def longest_run(nums: list[int]) -> int:
    """The length of the longest run of whole numbers in a row, like 4, 5, 6, in any order."""
    if not nums:
        return 0
    nums.sort()
    best = length = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            length += 1
        elif nums[i] != nums[i - 1]:  # a repeat doesn't end the run
            length = 1
        best = max(best, length)
    return best

Time

O(n log n)was O(n³)

Space

O(n)was O(1)

Why

The sort makes about n log₂ n comparisons, then one pass. While it sorts, Python’s sort can borrow room for up to n/2 items.

What changed from the previous rung

def longest_run(nums: list[int]) -> int:
    """The length of the longest run of whole numbers in a row, like 4, 5, 6, in any order."""
    best = 0
    for x in nums:
        length = 1
        while x + length in nums:  # looks through the whole list
    if not nums:
        return 0
    nums.sort()
    best = length = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            length += 1
        elif nums[i] != nums[i - 1]:  # a repeat doesn't end the run
            length = 1
        best = max(best, length)
    return best

Where it breaks: nums.sort() sorts the caller’s list, which the task says not to change. sorted(nums) would leave it alone, but it’s a full copy.

Best

A set, counting only from the start of each run

The idea: Put the numbers in a set. If x − 1 is there, x isn’t a start, so skip it. From each start, count up.

The waste in Better: it puts every number in order, when a run only needs “is the next number there?”, which a set answers in about one step.

The skip is what makes it O(n). Without it, a run of 100,000 would be counted again from each of its numbers: O(n²).

Highlighted lines are new in this rung.

def longest_run(nums: list[int]) -> int:
    """The length of the longest run of whole numbers in a row, like 4, 5, 6, in any order."""
    present = set(nums)
    best = 0
    for x in present:
        if x - 1 in present:
            continue  # x isn't the start of a run
        length = 1
        while x + length in present:
            length += 1
        best = max(best, length)
    return best

Time

O(n) on averagewas O(n log n)

Space

O(n)

Why

Each number is looked up as x − 1 once, and counted once, from the start of its run. The set holds every number.

What changed from the previous rung

def longest_run(nums: list[int]) -> int:
    """The length of the longest run of whole numbers in a row, like 4, 5, 6, in any order."""
    if not nums:
        return 0
    nums.sort()
    best = length = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
    present = set(nums)
    best = 0
    for x in present:
        if x - 1 in present:
            continue  # x isn't the start of a run
        length = 1
        while x + length in present:
            length += 1
        elif nums[i] != nums[i - 1]:  # a repeat doesn't end the run
            length = 1
        best = max(best, length)
    return best

When Best isn’t best: if you may change the list, or it’s already sorted, Better needs no set: the sort uses at most n/2 extra slots, and an already sorted list needs no sort at all.

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?

   from collections import Counter
   
   print(set('aab') == set('abb'))
   print(Counter('aab') == Counter('abb'))

   True, then TrueTrue, then FalseFalse, then FalseFalse, then True

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

   'ann'(1, 2)[1, 2]42

   Check answer
3. Spot the bugThis counts the words in a list. What goes wrong?

   def word_counts(words):
       counts = {}
       for w in words:
           counts[w] += 1
       return counts

   It counts each word twiceKeyError the first time a word is seenIt's O(n²)Nothing

   Check answer
4. Multiple choiced is a dict with n keys. Which of these is O(n)?

   'x' in dd['x'] = 15 in d.values()len(d)

   Check answer
5. Multiple choiceWhy is a dict lookup O(1) only on average?

   The dict sorts its keys now and thenKeys can clash on a slot, and then a look checks more than oneBig dicts are kept on diskStrings take longer to compare than numbers

   Check answer

Flashcards

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

• Card 1How does a dict find a key in about one step?Show answer
• Card 2What does a set forget that a dict of counts keeps?Show answer
• Card 3Three ways to count items with a dict?Show answer
• Card 4Which values can be dict keys?Show answer
• Card 5What are the four hash map patterns?Show answer
• Card 6How do you check two words are anagrams in O(n)?Show answer

Add 6 cards to my review deck

Cheat sheet

• A dict finds a key in about one step: O(1) on average, from the key’s hash. Clashes make the worst case O(n).
• Keys must be hashable: strings, numbers, and tuples of those. Not lists, dicts or sets, or a tuple that holds one.
• Count with d[x] = d.get(x, 0) + 1, Counter(...), or defaultdict(int).
• Group with defaultdict(list) and a key made from each item.
• A set keeps which items there are. A dict of counts keeps how many.
• Four patterns: count, seen, index (seen[value] = i), group.
• k in d checks keys in O(1). v in d.values() is O(n).
• Don’t change a dict’s keys while looping over it.

Go deeper

• In the Python docs: dict, and Counter and defaultdict.
• Draw your own: the Anagram check pictures on the DSA visualizer, and where a set looks.
• Two Sum uses the index pattern: a dict from each value to where it was.
• Next on the DSA roadmap: recursion.

Can you do these now?

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

• Say how a dict finds a key in about one step, and why that’s only true on average
• Count things with a dict, get(), Counter or defaultdict
• Spot the four hash map patterns, count, seen, index and group, in a new problem
• Say which keys a dict can take, and why a list can’t be one

✓Mark as completeI already know this

Status: Not started