My import got 100 times slower when the data grew 10 times

New to loops? Open the quick recap. It takes about two minutes.

Quick recapLoops and if in two minutes· 2 min

for x in items: runs the indented lines once for each item, with x set to it. if runs its lines only when its test is true, and x in items is a test: true when x is one of the items.

ids = [7, 3, 12]
for x in [5, 3]:
    if x in ids:
        print(x, "is known")    # 3 is known
    else:
        print(x, "is new")      # 5 is new

See the problem

Every night a job adds new users from a partner. It gets two lists of user ids: the ones you already have, and today’s file. It keeps the new ones:

def new_ids(known, incoming):
    return [x for x in incoming if x not in known]

Last month there were 1,000 of each, and it finished at once. Now there are 10,000 of each, and it takes about 100 times as long. Next year it will be 100,000 of each: 100 times longer again.

Why? x not in known compares x with the known ids one by one, and for a new id it has to check them all. 1,000 ids times 1,000 checks is up to 1 million comparisons. 10,000 times 10,000 is up to 100 million. Ten times the data, a hundred times the work.

And when the partner’s file has the same id twice, the job adds that user twice. How do you check “is it there?” without looking at everything?

Define the task

Write new_ids(known, incoming).

• Input: known, the user ids you already have, and incoming, today’s ids from the partner. Both are lists of whole numbers, up to 100,000 of each.
• Output: the ids in incoming that aren’t in known, each once, in the order they first come in incoming.
• The hard part: incoming can hold the same id twice. And it must be fast with 100,000 of each.

Example: new_ids([7, 3, 12], [5, 3, 9, 5, 7]) gives [5, 9].

Pause and think

⏸ Pause and think

To check whether 9 is in a list of 100,000 ids, Python may compare 9 with every one of them. What would let it check in one step?

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

Hints open one at a time:

Hint 1 of 3

x in a_list compares x with each item in turn, so it takes longer the more items there are.

Hint 2 of 3

A set works out where x would be from x itself. So x in a_set takes about the same time for 10 items or 10 million.

Hint 3 of 3

To skip a repeat in incoming, the set has to learn each new id as you find it.

Understand the idea

A list keeps its items in a row, in order. ids[2] jumps straight to the third item, whatever the list’s length. But 9 in ids can’t jump: it doesn’t know where 9 is, so it compares 9 with the first item, then the second, and so on. Twice the items, twice the work: that’s O(n).

A set is a table of slots. To add a number, Python works out a slot from the number itself, using its hash: a whole number made from the item. A whole number’s hash is the number itself, so in a table of 8 slots, 11 goes to slot 11 % 8 = 3. To find 11 later, Python works out slot 3 again and looks there. It doesn’t look at the other slots.

Watch numbers go into a set, then one get looked up. Under the table are the same numbers as a list, and at the end, how many of them a list would compare. Try your own, with whole numbers from 0 to 31: 3, 11, 19, 27 all want slot 3. (Bigger numbers mix more of their digits into the next slot, which makes the sums longer.)

Where a set looks

⤢ Full view

The set’s table: 8 slots

1. Slot 0: empty0
2. Slot 1: empty1
3. Slot 2: empty2
4. Slot 3: empty3
5. Slot 4: empty4
6. Slot 5: empty5
7. Slot 6: empty6
8. Slot 7: empty7

The same numbers in a list

None yet.

Step 1 of 11. seen = set() makes an empty set: a table of 8 slots, all empty.

◀ BackPlayNext ▶Reset Ask me first Show as text

1seen = set()
2for x in [3, 11, 6, 20, 14]:
3    seen.add(x)
4print(9 in seen)

Try your own input

Numbers to addLook forShow it

★Key insight

A set is fast because few items share a slot. Python keeps the table no more than about three fifths full, and makes a bigger one when it gets there, so a lookup almost always takes one look, or a few. That’s O(1) on average.

A dict is a set of keys, each with a value. d[key], d[key] = value and key in d work out the key’s slot from its hash too. Since Python 3.7, a dict also keeps its keys in the order you added them. A set doesn’t: it gives its items back in slot order.

Only things that can’t change can go in a set, or be a dict key. Numbers, text and tuples of them can. A list can’t: if it changed, its hash would change, and it would sit in the wrong slot. That’s the story of Python says my list can’t be a dict key. Text works like numbers, with one twist: Python mixes a random number into text hashes each time it starts. So a set of text can come back in a different order on each run.

A tuple is a list that can’t change. Use it for a fixed group of values, like a point (x, y) or a row (id, name). It can be a dict key, where a list can’t.

What each one costs, for n items. “On average” means when few items share a slot, which is almost always:

Operation	list	tuple	set	dict
x in c	O(n)	O(n)	O(1) on average	O(1) on average, for keys
get by position or key	c[i]: O(1)	c[i]: O(1)	none	d[k]: O(1) on average
add one	append(x): O(1) on average	can’t	add(x): O(1) on average	d[k] = v: O(1) on average
remove the last	pop(): O(1)	can’t	none	none
add or remove at the front	insert(0, x), pop(0): O(n)	can’t	none	none
remove a given one	remove(x): O(n)	can’t	discard(x): O(1) on average	del d[k]: O(1) on average
keeps order	yes	yes	no	yes, the order keys were added

Why is append() O(1) only on average? A list keeps a few spare spots at its end. When they run out, Python gets a bigger block of memory, with more spare room, and copies the items over if it has to. That copy is O(n), but it happens rarely enough that n appends still take O(n) steps in all.

Why is pop(0) slow? The items sit in a row from the front. Take the first away and every other item moves one place left. collections.deque (say “deck”) keeps both ends free: append(), appendleft(), pop() and popleft() are all O(1). It’s the queue to reach for.

from collections import deque

jobs = deque(["a", "b"])
jobs.append("c")      # deque(['a', 'b', 'c'])
jobs.popleft()        # 'a', in one step: nothing moves

Climb the ladder

All three give [5, 9] for the example without the repeat, new_ids([7, 3, 12], [5, 3, 9, 7]). What changes is how long they take, and what they do with a repeat.

Okay

Look through the known list

The idea: Keep each id in incoming that isn’t in known, with known still a list.

It’s one short line, and right for small lists with no repeats.

def new_ids(known: list[int], incoming: list[int]) -> list[int]:
    """The ids in incoming that aren't in known, each once, in the order they first come."""
    # known is a list, so each "not in" compares x with the known ids one by one.
    return [x for x in incoming if x not in known]

Time

O(n · m)

Space

O(m)

Why

For each of the m incoming ids, up to n comparisons with the known list.

Where it breaks: with 100,000 of each, up to 10 billion comparisons: it runs out of time. And [5, 9, 5] keeps both 5s.

Better

Make known a set

The idea: Turn known into a set once, then keep each id in incoming that isn’t in it.

The waste in Okay: it searches the same list again for every id, start to finish.

Building the set costs one pass over known. After that, each lookup is one slot, or a few. 100,000 of each is now about 200,000 steps, not 10 billion.

Highlighted lines are new in this rung.

def new_ids(known: list[int], incoming: list[int]) -> list[int]:
    """The ids in incoming that aren't in known, each once, in the order they first come."""
    known_set = set(known)  # "not in" on a set looks in one slot, or a few
    return [x for x in incoming if x not in known_set]

Time

O(n + m)

Space

O(n + m)

Why

n adds to build the set, then one lookup for each of the m incoming ids.

What changed from the previous rung

def new_ids(known: list[int], incoming: list[int]) -> list[int]:
    """The ids in incoming that aren't in known, each once, in the order they first come."""
    # known is a list, so each "not in" compares x with the known ids one by one.
    return [x for x in incoming if x not in known]
    known_set = set(known)  # "not in" on a set looks in one slot, or a few
    return [x for x in incoming if x not in known_set]

Where it breaks: the set only knows the old ids. An id that comes twice in incoming is new both times, so it comes back twice.

Best

A set that learns as it goes

The idea: Start the set from known. For each incoming id not in it, add it to the set, then to the answer.

The waste in Better: it finds a new id, then forgets it at once.

Adding each new id to seen means a repeat later on is found there and skipped. The list new keeps the order, which a set can’t.

Highlighted lines are new in this rung.

def new_ids(known: list[int], incoming: list[int]) -> list[int]:
    """The ids in incoming that aren't in known, each once, in the order they first come."""
    seen = set(known)
    new = []
    for x in incoming:
        if x not in seen:
            seen.add(x)  # so a repeat later in incoming is skipped too
            new.append(x)
    return new

Time

O(n + m)

Space

O(n + m)

Why

n adds, then for each incoming id one lookup and at most one add.

What changed from the previous rung

def new_ids(known: list[int], incoming: list[int]) -> list[int]:
    """The ids in incoming that aren't in known, each once, in the order they first come."""
    known_set = set(known)  # "not in" on a set looks in one slot, or a few
    return [x for x in incoming if x not in known_set]
    seen = set(known)
    new = []
    for x in incoming:
        if x not in seen:
            seen.add(x)  # so a repeat later in incoming is skipped too
            new.append(x)
    return new

When Best isn’t best: if order doesn’t matter, list(set(incoming) - set(known)) is shorter. And when the ids live in a database, let it check them with a unique key, instead of loading them all into Python.

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 fails the repeat and runs out of time on the speed test.

Find the new ids

Ctrl + Enter runs

def new_ids(known: list[int], incoming: list[int]) -> list[int]: # The ids in incoming that aren't in known, each once, # in the order they first come in incoming. return []

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

1. ○Not run yet: new_ids([7, 3, 12], [5, 3, 9, 7]) → [5, 9]
2. ○Not run yet: new_ids([], [4, 2]) → [4, 2]
3. ○Not run yet: new_ids([1], [30, 10, 20]) → [30, 10, 20]
4. ○Not run yet: new_ids([1], [5, 9, 5]) → [5, 9]
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 100,000 known ids and 100,000 incoming, half of them new

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

Try your own input

Arguments, separated by commas as in Python

new_ids()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: look through the known list	O(n · m)	O(m)	One short line	Far too slow for big lists; keeps repeats	The lists are tiny
Better: make known a set	O(n + m)	O(n + m)	Fast	Keeps repeats from incoming	incoming can’t repeat
Best: a set that learns as it goes	O(n + m)	O(n + m)	Fast, each id once, in order	A few more lines	Almost always

How much work is that? Each bar is one rung, with n ids in each list and none of them known. Better and Best both take about one set step per id.

New ids: steps with n ids in each list

1. OkayLook through the known list · O(n²)≈ 10,000,000,000 comparisons

2. BetterMake known a set · O(n)≈ 200,000 set steps

3. BestA set that learns as it goes · O(n)≈ 200,000 set steps

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

!{} is an empty dict, not a set

seen = {} makes a dict, and seen.add(3) then raises AttributeError: 'dict' object has no attribute 'add'. An empty set is set(). With items in it, {3, 11} is a set.

• A set has no order you can count on. It gives items back in slot order: list({20, 3, 14, 11, 6}) gives [3, 20, 6, 11, 14]. If order matters, keep a list beside the set, as Best does, or use a dict.
• in on a dict checks keys only. "Ann" in d.values() looks through every value: O(n).
• A slow step can hide in a loop. if x not in result: with result a list, items.count(x), items.index(x), items.remove(x) and items.pop(0) are all O(n). Inside a loop over n items, that’s O(n²).
• Don’t change a dict or set while you loop over it. Adding or removing raises RuntimeError: dictionary changed size during iteration (or Set changed size). Loop over a copy: for k in list(d):.
• A tuple of one needs a comma. (5,) is a tuple. (5) is just 5 in brackets.
• O(1) on average isn’t a promise. If many keys shared one slot, each lookup would check them all, like a list. That’s why Python mixes a random number into text hashes: so nobody can send keys that all clash on purpose.

Say it in the interview

Questions to ask first

• How big can the lists get, and how often does this run?
• Does the answer need to keep the order? Can ids repeat?
• Is memory tight? A set of n ids takes memory too.

A 60-second walkthrough

“The slow part is x not in known: on a list that’s a scan, so the whole thing is O(n times m). I’d turn known into a set first. A set finds an item by its hash, in one look on average. So each check is O(1) and the total is O(n plus m). Repeats in incoming need care: I add each new id to the same set as I find it, so the second copy is skipped. A separate list keeps the order, since a set doesn’t. That’s O(n plus m) time and O(n plus m) memory for the set.”

Likely follow-ups

• Why only O(1) on average? Items whose hashes clash share a chain of slots. With many clashes, a lookup checks them all. Python grows the table early, so that’s rare.
• When would you still use a list? When you need order, repeats or positions, and look things up rarely. A list also takes less memory than a set of the same items.
• What does append() cost? O(1) on average: the list keeps spare room and grows by more than one spot at a time.
• How would you make a queue? collections.deque, with append() and popleft(). A list’s pop(0) moves every other item.

Practice

Four 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. Keep the last lines (easy)

Write last_lines(lines, k), like tail -n k in a terminal: the last k lines, in order. lines can be a huge log file read one line at a time, so don’t keep more lines than you need. k is at least 1.

Example: last_lines(["a", "b", "c", "d"], 2) gives ["c", "d"].

Hint 1 of 3

list(lines) keeps every line of the file in memory, just to keep k of them.

Hint 2 of 3

Keep the last k lines as you go. But a list’s pop(0) moves every other line one place left.

Hint 3 of 3

deque(lines, maxlen=k) keeps at most k: when it’s full, adding one drops the oldest, in one step.

Keep the last lines

Ctrl + Enter runs

from collections.abc import Iterable def last_lines(lines: Iterable[str], k: int) -> list[str]: # The last k lines, in order. k is at least 1. return []

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

1. ○Not run yet: last_lines(['a', 'b', 'c', 'd'], 2) → ['c', 'd']
2. ○Not run yet: last_lines(['a', 'b'], 3) → ['a', 'b']
3. ○Not run yet: last_lines(['a', 'b', 'c'], 3) → ['a', 'b', 'c']
4. ○Not run yet: Extra test
5. ○Not run yet: A log of 200,000 lines, read one at a time: the last 10, in 1 MB
6. ○Not run yet: Speed test: the last 100,000 of 600,000 lines (how many, the first, the last) → [100000, 'line 500000', 'line 599999']

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

Try your own input

Arguments, separated by commas as in Python

last_lines()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Read them all, keep the end

The idea: list(lines)[-k:]

One line, and fast.

from collections.abc import Iterable


def last_lines(lines: Iterable[str], k: int) -> list[str]:
    """The last k lines, in order."""
    return list(lines)[-k:]  # holds every line first

Time

O(n)

Space

O(n)

Why

Reads all n lines once, and keeps every one of them.

Where it breaks: it keeps the whole file in memory to give back 10 lines. A 200,000-line log needs megabytes; a 10 GB log won’t fit.

Better

Keep k lines in a list

The idea: Append each line. When there are more than k, pop(0) the oldest.

The waste in Okay: it keeps lines it already knows it won’t give back.

Now at most k + 1 lines are kept at once.

Highlighted lines are new in this rung.

from collections.abc import Iterable


def last_lines(lines: Iterable[str], k: int) -> list[str]:
    """The last k lines, in order."""
    last: list[str] = []
    for line in lines:
        last.append(line)
        if len(last) > k:
            last.pop(0)  # moves every other line one place to the left
    return last

Time

O(n · k)

Space

O(k)

Why

Each pop(0) moves the other k lines one place left.

What changed from the previous rung

from collections.abc import Iterable


def last_lines(lines: Iterable[str], k: int) -> list[str]:
    """The last k lines, in order."""
    return list(lines)[-k:]  # holds every line first
    last: list[str] = []
    for line in lines:
        last.append(line)
        if len(last) > k:
            last.pop(0)  # moves every other line one place to the left
    return last

Where it breaks: pop(0) is O(k). With 600,000 lines and k = 100,000, that’s 500,000 pops of 100,000 moves each: 50 billion moves, and it runs out of time.

Best

A deque with maxlen

The idea: list(deque(lines, maxlen=k))

The waste in Better: it moves k lines to drop one.

A deque adds at one end and drops at the other without moving anything. With maxlen, it drops the oldest by itself once it holds k.

Highlighted lines are new in this rung.

from collections import deque
from collections.abc import Iterable


def last_lines(lines: Iterable[str], k: int) -> list[str]:
    """The last k lines, in order."""
    # A deque adds and drops at either end in one step; maxlen drops the oldest for you.
    return list(deque(lines, maxlen=k))

Time

O(n)

Space

O(k)

Why

Each line is added, and the oldest dropped, in one step; at most k are kept.

What changed from the previous rung

from collections import deque
from collections.abc import Iterable


def last_lines(lines: Iterable[str], k: int) -> list[str]:
    """The last k lines, in order."""
    last: list[str] = []
    for line in lines:
        last.append(line)
        if len(last) > k:
            last.pop(0)  # moves every other line one place to the left
    return last
    # A deque adds and drops at either end in one step; maxlen drops the oldest for you.
    return list(deque(lines, maxlen=k))

When Best isn’t best: for a file on disk, reading backwards from the end, as tail does, skips the whole start of the file. That’s faster for a huge log, but harder to get right.

2. Add up two days of sales (easy)

Write merge_totals(a, b). a and b are two days of sales, each a dict from a product’s name to the amount sold. A refund makes an amount negative. Give back a new dict with each product’s total over both days. A product sold on one day only keeps that day’s amount, and a total of 0 stays in. Don’t change a or b: other code still reads them.

Example: merge_totals({"tea": 3, "cake": 2}, {"tea": 1, "milk": 4}) gives {"tea": 4, "cake": 2, "milk": 4}.

Hint 1 of 3

{**a, **b} puts both dicts into one, but for a name in both, b’s amount replaces a’s. You want them added.

Hint 2 of 3

Go through b and add each amount to the total so far, with get(name, 0) for a name that isn’t there yet. But which dict are you adding to?

Hint 3 of 3

merged = a doesn’t copy anything: both names now point at the same dict, so adding to merged changes a. Start from a copy: dict(a).

Add up two days of sales

Ctrl + Enter runs

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]: # A new dict: each product's total over both days. # Don't change a or b. return {}

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

1. ○Not run yet: merge_totals({'tea': 3, 'cake': 2}, {'tea': 1, 'milk': 4}) → {'tea': 4, 'cake': 2, 'milk': 4}
2. ○Not run yet: merge_totals({}, {'tea': 1}) → {'tea': 1}
3. ○Not run yet: merge_totals({'tea': 2}, {'tea': -2}) → {'tea': 0}
4. ○Not run yet: merge_totals({'tea': 5}, {'cake': -1}) → {'tea': 5, 'cake': -1}
5. ○Not run yet: Extra test

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

Try your own input

Arguments, separated by commas as in Python

merge_totals()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Put both dicts into one

The idea: {**a, **b}: every key from a, then every key from b.

One line, and right when no product is in both.

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]:
    return {**a, **b}

Time

O(n + m)

Space

O(n + m)

Why

One pass over each dict to build the new one.

Where it breaks: a dict holds one value for each key, so for a name in both, b’s amount replaces a’s: tea comes out as 1, not 4.

Better

Add b’s amounts to a

The idea: For each name in b, total = what’s there so far (or 0) + b’s amount.

The waste in Okay: it drops a’s amount instead of adding it.

merged.get(name, 0) gives the total so far, or 0 for a name a didn’t have, so every total is right.

Highlighted lines are new in this rung.

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]:
    merged = a
    for name, amount in b.items():
        merged[name] = merged.get(name, 0) + amount
    return merged

Time

O(m)

Space

O(1)

Why

One look-up and one store for each of b’s m names; nothing new is made.

What changed from the previous rung

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]:
    return {**a, **b}
    merged = a
    for name, amount in b.items():
        merged[name] = merged.get(name, 0) + amount
    return merged

Where it breaks: merged = a makes a second name for the same dict, not a copy. So adding to merged changes a, and any code still reading day one sees both days. More on this in I changed my copy, and the original changed too.

Best

Copy a, then add b

The idea: merged = dict(a), then add each of b’s amounts to merged.

The waste in Better: nothing, it’s a bug: it writes into a dict that isn’t its own.

dict(a) makes a new dict with the same keys and amounts. Adding to it leaves a as it was.

Highlighted lines are new in this rung.

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]:
    merged = dict(a)  # a new dict, so a stays as it was
    for name, amount in b.items():
        merged[name] = merged.get(name, 0) + amount
    return merged

Time

O(n + m)

Space

O(n + m)

Why

The copy takes one pass over a; then one look-up and store for each name in b.

What changed from the previous rung

def merge_totals(a: dict[str, int], b: dict[str, int]) -> dict[str, int]:
    merged = a
    merged = dict(a)  # a new dict, so a stays as it was
    for name, amount in b.items():
        merged[name] = merged.get(name, 0) + amount
    return merged

When Best isn’t best: Counter(a) + Counter(b) is one line, but it drops every total of 0 or less, so a refunded product disappears. Counter(a), then .update(b), keeps them; use it when you also want Counter’s other methods, like most_common().

3. Name each order’s customer (medium)

You have the customers, as (id, name) pairs, and the orders, as (order_id, customer_id) pairs. Write customer_names(customers, orders): the customer’s name for each order, in order. If an order’s customer id isn’t a customer, its name is "unknown". Each customer id comes once in customers.

Example: with customers [(1, "Ann"), (2, "Bo")] and orders [(100, 2), (101, 1), (102, 2)], it gives ["Bo", "Ann", "Bo"].

Hint 1 of 3

Looking through all the customers for each order is O(customers × orders).

Hint 2 of 3

dict(customers) builds an id → name lookup in one pass, and each lookup is O(1) on average.

Hint 3 of 3

Looking up a missing key with square brackets raises KeyError. d.get(key, default) gives the default instead.

Name each order’s customer

Ctrl + Enter runs

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]: # The customer's name for each order, in order, # or "unknown" when the id isn't a customer. return []

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

1. ○Not run yet: customer_names([(1, "Ann"), (2, "Bo")], [(100, 2), (101, 1), (102, 2)]) → ['Bo', 'Ann', 'Bo']
2. ○Not run yet: customer_names([(1, "Ann")], []) → []
3. ○Not run yet: customer_names([(1, "Ann")], [(100, 3)]) → ['unknown']
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 50,000 customers and 50,000 orders (the first three names, and how many) → ['user 0', 'user 7919', 'user 15838', 50000]

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

Try your own input

Arguments, separated by commas as in Python

customer_names()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Look through the customers for each order

The idea: For each order, loop over the customers until the id matches; else unknown.

Clear, and right, unknown ids included.

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]:
    """The customer's name for each order, or "unknown" when the id isn't a customer."""
    names = []
    for _order_id, customer_id in orders:
        name = "unknown"
        for cid, cname in customers:  # looks through every customer, for every order
            if cid == customer_id:
                name = cname
                break
        names.append(name)
    return names

Time

O(c · o)

Space

O(o)

Why

Up to c customer checks for each of the o orders.

Where it breaks: with 50,000 of each, up to 2.5 billion checks: it runs out of time.

Better

Build a dict, then look each one up

The idea: by_id = dict(customers), then by_id[customer_id] for each order.

The waste in Okay: it searches the same customers again for every order.

dict() turns the pairs into id → name in one pass. This is the same idea as a join in SQL: build a lookup once, then use it many times.

Highlighted lines are new in this rung.

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]:
    """The customer's name for each order, or "unknown" when the id isn't a customer."""
    by_id = dict(customers)  # id -> name, built once
    return [by_id[customer_id] for _order_id, customer_id in orders]

Time

O(c + o)

Space

O(c + o)

Why

One pass to build the dict, then one lookup per order.

What changed from the previous rung

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]:
    """The customer's name for each order, or "unknown" when the id isn't a customer."""
    names = []
    for _order_id, customer_id in orders:
        name = "unknown"
        for cid, cname in customers:  # looks through every customer, for every order
            if cid == customer_id:
                name = cname
                break
        names.append(name)
    return names
    by_id = dict(customers)  # id -> name, built once
    return [by_id[customer_id] for _order_id, customer_id in orders]

Where it breaks: by_id[3] raises KeyError: 3 when 3 isn’t a customer.

Best

The same dict, with get()

The idea: by_id.get(customer_id, "unknown") for each order.

The waste in Better: one missing id stops the whole list.

get() gives back the default when the key isn’t there, in the same one lookup.

Highlighted lines are new in this rung.

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]:
    """The customer's name for each order, or "unknown" when the id isn't a customer."""
    by_id = dict(customers)  # id -> name, built once
    return [by_id.get(customer_id, "unknown") for _order_id, customer_id in orders]

Time

O(c + o)

Space

O(c + o)

Why

One pass to build the dict, then one lookup per order.

What changed from the previous rung

def customer_names(customers: list[tuple[int, str]], orders: list[tuple[int, int]]) -> list[str]:
    """The customer's name for each order, or "unknown" when the id isn't a customer."""
    by_id = dict(customers)  # id -> name, built once
    return [by_id[customer_id] for _order_id, customer_id in orders]
    return [by_id.get(customer_id, "unknown") for _order_id, customer_id in orders]

When Best isn’t best: when the data is in a database, a LEFT JOIN does this, with COALESCE(name, 'unknown'), without loading every customer into Python.

4. A repeat within k places (hard)

Write repeat_within(nums, k): True if some number comes twice, at most k places apart. That is, nums[i] == nums[j] for some i < j with j - i <= k. Lists can be long, and k can be big or small, so watch time and memory.

Examples: repeat_within([1, 2, 3, 1], 3) gives True: the two 1s are 3 places apart. repeat_within([1, 2, 3, 1], 2) gives False.

Hint 1 of 3

Checking the next k numbers for each number is O(n · k). A slice copies them too.

Hint 2 of 3

A dict of where each number was last seen answers in O(1). But it remembers every number, even ones far behind.

Hint 3 of 3

Only the last k numbers can be a repeat. Keep them in a set: add the new one, and remove the one now more than k places back.

A repeat within k places

Ctrl + Enter runs

def repeat_within(nums: list[int], k: int) -> bool: # True if some number comes twice, at most k places apart. return False

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

1. ○Not run yet: repeat_within([1, 2, 3, 1], 3) → True
2. ○Not run yet: repeat_within([1, 2, 3, 1], 2) → False
3. ○Not run yet: repeat_within([5, 5], 1) → True
4. ○Not run yet: Extra test
5. ○Not run yet: 200,000 different numbers, k = 10, in 1 MB → False
6. ○Not run yet: Speed test: 100,000 different numbers, k = 50,000 → False

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

Try your own input

Arguments, separated by commas as in Python

repeat_within()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Search the next k numbers

The idea: For each number, check whether it’s in the slice of the next k.

Short, and it says exactly what the problem says.

def repeat_within(nums: list[int], k: int) -> bool:
    """True if some number comes twice, at most k places apart."""
    # For each number, copy the next k numbers and search them.
    return any(x in nums[i + 1 : i + k + 1] for i, x in enumerate(nums))

Time

O(n · k)

Space

O(k)

Why

Each of the n numbers copies and searches up to k numbers.

Where it breaks: with 100,000 numbers and k = 50,000, billions of copies and checks: it runs out of time.

Better

Remember where each number was last

The idea: A dict of number → last place. A repeat is close enough if i - last_at[x] <= k.

The waste in Okay: it checks the same numbers again and again, as the window slides along one place.

Now each number is one lookup, however big k is.

Highlighted lines are new in this rung.

def repeat_within(nums: list[int], k: int) -> bool:
    """True if some number comes twice, at most k places apart."""
    last_at: dict[int, int] = {}  # each number -> where it was last seen
    for i, x in enumerate(nums):
        if x in last_at and i - last_at[x] <= k:
            return True
        last_at[x] = i
    return False

Time

O(n)

Space

O(n)

Why

One dict lookup and one update per number; the dict holds every different number.

What changed from the previous rung

def repeat_within(nums: list[int], k: int) -> bool:
    """True if some number comes twice, at most k places apart."""
    # For each number, copy the next k numbers and search them.
    return any(x in nums[i + 1 : i + k + 1] for i, x in enumerate(nums))
    last_at: dict[int, int] = {}  # each number -> where it was last seen
    for i, x in enumerate(nums):
        if x in last_at and i - last_at[x] <= k:
            return True
        last_at[x] = i
    return False

Where it breaks: the dict keeps every number it has seen, even ones far more than k places back. 200,000 different numbers fill megabytes, when k = 10 needs only 10.

Best

A set of the last k numbers

The idea: If x is in the set, it’s a repeat. Add x; if the set holds more than k, remove the number k places back.

The waste in Better: it remembers numbers that can never be a repeat again.

The set is a sliding window: it holds exactly the last k numbers. They’re all different, or the code would already have returned True, so removing nums[i - k] removes just that one number.

Highlighted lines are new in this rung.

def repeat_within(nums: list[int], k: int) -> bool:
    """True if some number comes twice, at most k places apart."""
    window: set[int] = set()  # the last k numbers
    for i, x in enumerate(nums):
        if x in window:
            return True
        window.add(x)
        if len(window) > k:
            window.remove(nums[i - k])  # the number now more than k places back
    return False

Time

O(n)

Space

O(k)

Why

One lookup, one add and at most one remove per number; at most k numbers kept.

What changed from the previous rung

def repeat_within(nums: list[int], k: int) -> bool:
    """True if some number comes twice, at most k places apart."""
    last_at: dict[int, int] = {}  # each number -> where it was last seen
    window: set[int] = set()  # the last k numbers
    for i, x in enumerate(nums):
        if x in last_at and i - last_at[x] <= k:
        if x in window:
            return True
        last_at[x] = i
        window.add(x)
        if len(window) > k:
            window.remove(nums[i - k])  # the number now more than k places back
    return False

When Best isn’t best: when k is bigger than the list, the window never slides, and the set holds every number, the same as Better. Then len(set(nums)) < len(nums) says whether there’s any repeat at all, in one line.

Check yourself

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

1. Pick the patternA loop checks 100,000 times whether a user id is in a list of 100,000 ids. What makes it fast, without changing the answer?

   Sort the list firstTurn the list into a set once, before the loop, and check the setUse a tuple instead of the listCheck with ids.index(x) instead of x in ids

   Check answer
2. Predict the outputWhat does this print?

   seen = set()
   for x in [3, 11, 3, 11]:
       seen.add(x)
   print(len(seen))

   421An error: 3 and 11 want the same slot

   Check answer
3. Spot the bugThis keeps the last 50,000 lines of a big log. Why is it slow?

   last = []
   for line in log:
       last.append(line)
       if len(last) > 50_000:
           last.pop(0)

   append() copies the whole list every timepop(0) moves every other line one place left, so each one is O(n)len() counts the lines one by oneA list can’t hold more than 50,000 lines

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

   [1, 2]{1, 2}(1, 2){"a": 1}

   Check answer
5. Predict the outputWhat does this print?

   d = {"Ann": 1, "Bo": 2}
   print(2 in d, "Bo" in d)

   True TrueFalse TrueTrue FalseFalse False

   Check answer

Flashcards

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

• Card 1Why is x in a_set fast and x in a_list slow?Show answer
• Card 2What do append(), pop(), pop(0) and insert(0, x) cost on a list?Show answer
• Card 3When do you reach for collections.deque?Show answer
• Card 4What can be a set item or a dict key?Show answer
• Card 5Does a set keep the order you added things in?Show answer

Add 5 cards to my review deck

Cheat sheet

• x in a_list compares one by one: O(n). x in a_set and key in a_dict look in one slot, or a few: O(1) on average.
• Turn a list into a set once, before a loop that checks it many times.
• A list keeps order and repeats. A set keeps one of each, in no order you can count on. A dict keeps one value per key, in the order keys were added.
• append() and pop() are O(1) at the end. insert(0, x), pop(0), remove(x), index(x) and count(x) are O(n).
• Need both ends? collections.deque. Need only the last k? deque(maxlen=k).
• Set items and dict keys must be hashable: numbers, text, tuples of them. Not lists.
• An empty set is set(). {} is an empty dict.

Go deeper

• In the Python docs: the time each operation takes on list, set and dict, set and dict, and deque.
• From the Python glossary: hashable.
• Draw your own: the set picture on the Python visualizer.
• Next on the Python roadmap: Python says my formula has too many nested parentheses, on what happens when you press Run. Then I changed my copy, and the original changed too, on what a name really holds.

Can you do these now?

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

• Say what in, append, pop(0), insert and a lookup cost on list, tuple, dict and set
• Explain how a set or dict finds an item without looking at every one
• Pick a container by the operations you'll do most, and use deque for both ends
• Spot a slow step hidden inside a loop

✓Mark as completeI already know this

Status: Not started