My code passed every test, then timed out on the big one

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

Quick recapFunctions and loops in two minutes· 2 min

def makes a function, and return hands back its answer and ends the call at once, even from inside a loop. range(a, b) counts from a up to b - 1, and ids[i] is the item at position i, counting from 0.

def first_big(nums):
    for i in range(len(nums)):     # i = 0, 1, 2, ...
        if nums[i] > 10:
            return i               # stops here: the rest isn't checked
    return -1

first_big([4, 12, 30])    # 1

Quick recapSets in two minutes· 2 min

A set keeps one of each item. x in a_set works out where x would be from x itself, so it takes about one step however big the set is: O(1) on average. x in a_list compares x with the items one by one.

seen = set()      # an empty set ({} is an empty dict)
seen.add(41)
seen.add(41)      # already there: still one 41
41 in seen        # True, in about one step
len(seen)         # 1

See the problem

You’re practising for an interview. The task: a shop must never charge an order twice, so before it pays out, it checks the day’s order ids for a repeat. You write:

def has_duplicate(ids):
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

The small tests pass at once. The last test has 100,000 ids, and it stops: too slow.

The code is right. It’s just slow, and nothing in the small tests warned you. Could you have known before you pressed Run? Yes: count the work.

With 5 ids, the loops compare 4 + 3 + 2 + 1 = 10 pairs. With 1,000 ids, about 500,000 pairs. With 100,000 ids, about 5 billion. Python does a few tens of millions of these checks a second. So that’s about two minutes on a laptop, for one check of one day.

Define the task

Write has_duplicate(ids).

• Input: ids, a list of whole numbers: the day’s order ids. Up to 100,000 of them.
• Output: True if some id comes more than once, else False.
• The hard part: it must be fast with 100,000 ids. And it mustn’t change ids: the code after it still uses the list, in the order the orders came in.

Example: has_duplicate([4, 9, 2, 9]) gives True. has_duplicate([4, 9, 2]) gives False.

Pause and think

⏸ Pause and think

Before you write any code: if the ids double from 50,000 to 100,000, how much longer do the two loops take? Twice as long, or more?

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

Hints open one at a time:

Hint 1 of 3

Each id is compared with every id after it. Double the ids, and each one has about twice as many to compare with.

Hint 2 of 3

Twice as many ids, each with twice as many comparisons, is four times the work. That’s O(n²).

Hint 3 of 3

To get down to about one step per id, you need to ask “have I seen this id before?” without looking back through the list.

Understand the idea

Count steps, not seconds. Seconds depend on the computer, and on what else it’s doing. The number of steps doesn’t. A step is one small thing: compare two numbers, add two numbers, look in a set.

Watch the two loops on 5 ids. The panel beside the list counts the pair checks. Try your own ids, 2 to 7 of them: with no repeat, every pair is checked.

Check every pair

⤢ Full view

1. 410
2. 171
3. 82
4. 333
5. 254

Work so far

pair checks	0

Step 1 of 12. Compare every pair of the 5 ids, looking for two the same. Question: With 5 ids, how many pair checks can it take, at most?

What happens next? With 5 ids, how many pair checks can it take, at most?

5102025Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def has_duplicate(ids: list[int]) -> bool:
2    # Compare every pair once: ids[i] with each id after it.
3    for i in range(len(ids)):
4        for j in range(i + 1, len(ids)):
5            if ids[i] == ids[j]:
6                return True
7    return False

Try your own input

IdsShow it

Big-O says how the count grows. For n ids with no repeat, the loops make n(n − 1)/2 pair checks: for big n, about n²/2. Big-O keeps only the part that grows fastest and drops the number in front of it, so this is O(n²). Why drop it? Big-O answers one question: when n gets 10 times bigger, how much more work is there? For n²/2 and for n², the answer is the same: 100 times.

★Key insight

Ask what happens when n doubles. O(1): no change. O(log n): one more step. O(n): twice the work. O(n²): four times. O(2ⁿ): the work is squared.

How the steps grow, for each Big-O you’ll meet most:

Big-O	Called	Example	n = 10	n = 1,000	n = 100,000
O(1)	constant	ids[0], or x in a_set on average	1	1	1
O(log n)	logarithmic	binary search: halve a sorted list until one item is left	3	10	17
O(n)	linear	one loop over the list	10	1,000	100,000
O(n log n)	n log n	sorting	33	10,000	1.7 million
O(n²)	quadratic	every pair: a loop inside a loop	100	1 million	10 billion
O(2ⁿ)	exponential	every subset of the list	1,024	a 302-digit number	a 30,103-digit number

A rough guide for Python, which does about 10 to 50 million simple steps a second. In about a second:

• O(n) and O(n log n) handle up to about a million items.
• O(n²) handles a few thousand.
• O(2ⁿ) handles about 20.

So when an interview problem says n can be 100,000, that’s a hint: the answer must be O(n log n) or better.

Best case and worst case. If the first two ids match, the loops stop after one check. If no id repeats, they check every pair. Big-O usually means the worst case: the most work any input of size n can make. When it’s an average, say so: a set lookup is O(1) on average.

Space is the extra memory. Big-O works the same way for memory: how much more does the code keep as n grows? The two loops keep two numbers, i and j, whatever n is: O(1). A set of every id seen so far is O(n). Don’t count the input itself, but do count anything you copy from it: sorted(ids), ids[:] and a slice like ids[:j] each make a new list.

Steps one after another add. Steps inside each other multiply. A loop over n orders, then a loop over m customers: O(n + m). A loop over m customers inside a loop over n orders: O(n · m). And watch for loops you can’t see. x in a_list, a_list.index(x), sum(), max(), sorted() and a slice each go through the list, so each one inside a loop is a loop inside a loop. My import got 100 times slower when the data grew 10 times lists what each list, dict and set operation costs.

Climb the ladder

All three give True for [4, 9, 2, 9]. What changes is how the work grows, and what they do to ids.

Okay

Check every pair

The idea: Compare each id with every id after it. Two the same is a repeat.

Clear, right, and it changes nothing. For a few hundred ids, it’s fine.

def has_duplicate(ids: list[int]) -> bool:
    # Compare every pair once: ids[i] with each id after it.
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

Time

O(n²)

Space

O(1)

Why

n(n − 1)/2 pair checks when nothing repeats. Only i and j are kept.

Where it breaks: speed. 100,000 ids is about 5 billion pair checks: about two minutes in Python. The editor below stops it after 3 seconds.

Better

Sort, then check neighbours

The idea: After sorting, two ids the same sit side by side, so compare each id with the one before it.

The waste in Okay: it compares ids that are far apart in value, again and again. Once the ids are sorted, a repeat can only sit next to its twin, so one pass over the neighbours finds it.

100,000 ids now take about 1.8 million steps, not 5 billion.

Highlighted lines are new in this rung.

def has_duplicate(ids: list[int]) -> bool:
    # Sort, and any repeats end up side by side.
    ids.sort()
    return any(ids[i] == ids[i - 1] for i in range(1, len(ids)))

Time

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

Space

O(n)was O(1)

Why

The sort makes about n log₂ n comparisons (1.7 million for 100,000 ids), 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 has_duplicate(ids: list[int]) -> bool:
    # Compare every pair once: ids[i] with each id after it.
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False
    # Sort, and any repeats end up side by side.
    ids.sort()
    return any(ids[i] == ids[i - 1] for i in range(1, len(ids)))

Where it breaks: ids.sort() sorts the caller’s list. After the check, the day’s orders are in id order, not the order they came in. The code that prints them next prints them wrong. sorted(ids) would leave ids alone, but it makes a full copy.

Best

A set of the ids seen so far

The idea: For each id, look in a set of the ids before it. In there: a repeat. Not there: add it.

The waste in Better: it puts every id in order, when all it needs to know is whether each id came before. A set answers that in about one look, however many ids it holds.

It never changes ids, and it stops at the first repeat. Watch the panel: one look for each id, where Okay made a pair check for every pair.

A set of the ids seen so far

⤢ Full view

1. 410
2. 171
3. 82
4. 173
5. 254

Work so far

looks in seen	0
adds to seen	0

Step 1 of 9. Start with an empty set, seen. Question: With 5 ids, how many looks in seen can it take, at most?

What happens next? With 5 ids, how many looks in seen can it take, at most?

51025Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def has_duplicate(ids: list[int]) -> bool:
2    seen: set[int] = set()
3    for x in ids:
4        if x in seen:  # one look in the set, however big it is
5            return True
6        seen.add(x)
7    return False

Try your own input

IdsShow it

Highlighted lines are new in this rung.

def has_duplicate(ids: list[int]) -> bool:
    seen: set[int] = set()
    for x in ids:
        if x in seen:  # one look in the set, however big it is
            return True
        seen.add(x)
    return False

Time

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

Space

O(n)

Why

One look and at most one add for each id, each O(1) on average. The set can end up holding every id.

What changed from the previous rung

def has_duplicate(ids: list[int]) -> bool:
    # Sort, and any repeats end up side by side.
    ids.sort()
    return any(ids[i] == ids[i - 1] for i in range(1, len(ids)))
    seen: set[int] = set()
    for x in ids:
        if x in seen:  # one look in the set, however big it is
            return True
        seen.add(x)
    return False

When Best isn’t best: when the list is yours to change and memory is tight. Both are O(n) memory. But in CPython, the set for 100,000 ids takes about 4 MB, and the sort uses about 0.4 MB extra. Big-O hides that difference. And if the ids come already sorted, skip the sort: checking neighbours is O(n) time and O(1) memory.

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 test that checks ids is left as it was.

Check for a repeated id

Ctrl + Enter runs

def has_duplicate(ids: list[int]) -> bool: # True if some id comes more than once. # Don't change ids. return False

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

1. ○Not run yet: has_duplicate([4, 9, 2, 9]) → True
2. ○Not run yet: has_duplicate([4, 9, 2]) → False
3. ○Not run yet: has_duplicate([]) → False
4. ○Not run yet: Extra test
5. ○Not run yet: has_duplicate([5, 1, 5]), and ids must not change → True
6. ○Not run yet: Speed test: 100,000 different ids, in mixed order → 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

has_duplicate()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: check every pair	O(n²)	O(1)	Short, and changes nothing	Far too slow past a few thousand ids	The list is tiny
Better: sort, then check neighbours	O(n log n)	O(n), up to n/2 spare slots	Fast, and light on memory	Sorts the caller’s list	The list is yours to change, and memory is tight
Best: a set of the ids seen so far	O(n) on average	O(n)	Fast, changes nothing, stops at the first repeat	The set takes more memory	Almost always

How much work is that? Each bar is one rung, with n ids and no repeat: the worst case. Pick a size, or run the race.

Repeated ids: steps with n ids and no repeat

1. OkayCheck every pair · O(n²)≈ 5,000,000,000 pair checks

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

3. BestA set of the ids seen so far · O(n) on average≈ 100,000 set looks

At n = 100,000, Okay does about 50,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.

Common mistakes and edge cases

!A slice in a loop is a loop in a loop

if ids[j] in ids[:j]: reads like one step. But the slice copies up to j ids, and in then searches them: O(n) each time round, so O(n²) in all, and O(n) memory for the copy.

• The same Big-O isn’t the same cost. Big-O drops the constants, so two O(n) answers can differ ten times in speed or memory, like the set and the sort above. To choose between them, measure.
• O(n log n) is nearly O(n). log₂ of 100,000 is about 17. Sorting first is often fast enough, and it can make a problem much easier.
• Keep two sizes apart. A loop over m customers inside a loop over n orders is O(n · m), not O(n²). Say which letter is which.
• Count what you keep, not just what you loop over. sorted(ids), list(...), ids[:] and [x for x in ids] each take O(n) memory. f.readlines() keeps every line of the file.
• O(1) on average isn’t a promise. A set or dict lookup is O(1) on average. If many keys clashed, it would be O(n). In an interview, say “on average”.
• The best case isn’t the answer. “It’s O(1) when the first two ids match” is true, but the question means the worst case unless it says otherwise.

Say it in the interview

Questions to ask first

• How many ids can there be? That tells you which Big-O is fast enough.
• May I change the list, or sort it?
• Is memory tight?
• Could the ids already be sorted?

A 60-second walkthrough

“The simple way compares every pair: n times n minus one over two checks, so O(n squared) time and O(1) space. With 100,000 ids that’s about 5 billion checks, far too slow. Sorting first puts repeats side by side, so one pass after the sort finds them: O(n log n). But sort changes the caller’s list. So I’d keep a set of the ids seen so far: for each id, if it’s in the set, return True, else add it. Each look is O(1) on average, so that’s O(n) time and O(n) space, and it stops at the first repeat.”

Likely follow-ups

• Can you do it in O(1) extra memory? Sort the list in place, if you may change it: O(n log n) time. Python’s own sort still uses some extra memory while it works; a heapsort wouldn’t.
• What if the ids are already sorted? Check neighbours: O(n) time, O(1) memory, no sort.
• Why is the set only O(1) on average? Ids whose hashes clash share slots, and with many clashes a look checks them all. Python keeps plenty of empty slots in the table, so that’s rare.
• What does “amortized” mean? Averaged over many operations. Now and then seen.add() makes the set bigger and copies it, which is O(n). It happens rarely enough that n adds still take O(n) in all, so each add is O(1) amortized.

Practice

Three problems, from easy to medium. 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. The first repeated id (easy)

Write first_repeat(ids): the first id to show up a second time, or None if none does. “First” means the earliest second copy.

Example: first_repeat([5, 1, 1, 5]) gives 1. The second 1 is at index 2, before the second 5 at index 3.

Hint 1 of 3

ids[j] in ids[:j] reads well, but the slice copies up to j ids, then searches them. Inside a loop, that’s O(n²).

Hint 2 of 3

Counting every id first tells you which ids repeat. Does it tell you which repeat comes first?

Hint 3 of 3

Walk the list once with a set of the ids so far. The first id that’s already in it is the answer.

The first repeated id

Ctrl + Enter runs

def first_repeat(ids: list[int]) -> int | None: # The first id to show up a second time, or None. return None

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

1. ○Not run yet: first_repeat([5, 1, 1, 5]) → 1
2. ○Not run yet: first_repeat([3, 8, 3, 8]) → 3
3. ○Not run yet: first_repeat([2, 7, 4]) → None
4. ○Not run yet: first_repeat([]) → None
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 100,000 different ids, then 0 again → 0

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

Search the ids before each one

The idea: For each id, check whether it’s in the slice of the ids before it.

Short, and it says just what the problem says.

def first_repeat(ids: list[int]) -> int | None:
    """The first id to show up a second time, or None."""
    for j in range(len(ids)):
        if ids[j] in ids[:j]:  # a copy of the ids so far, then a search through it
            return ids[j]
    return None

Time

O(n²)

Space

O(n)

Why

Each of the n ids copies up to n ids before it, then searches them.

Where it breaks: with 100,000 different ids, about 5 billion copies and checks: it runs out of time.

Better

Count every id, then find one that repeats

The idea: Counter(ids), then the first id in the list whose count is more than 1.

The waste in Okay: it searches the same ids again for every id. Counting them once is O(n).

Highlighted lines are new in this rung.

from collections import Counter


def first_repeat(ids: list[int]) -> int | None:
    """The first id to show up a second time, or None."""
    counts = Counter(ids)
    for x in ids:
        if counts[x] > 1:
            return x
    return None

Time

O(n)

Space

O(n)

Why

One pass to count, then one pass to find. The counts hold every different id.

What changed from the previous rung

from collections import Counter


def first_repeat(ids: list[int]) -> int | None:
    """The first id to show up a second time, or None."""
    for j in range(len(ids)):
        if ids[j] in ids[:j]:  # a copy of the ids so far, then a search through it
            return ids[j]
    counts = Counter(ids)
    for x in ids:
        if counts[x] > 1:
            return x
    return None

Where it breaks: it finds the first id that has a repeat, not the first repeat. In [5, 1, 1, 5], 5 comes first and has a repeat, so it gives 5. But the 1s repeat first.

Best

A set of the ids so far

The idea: Walk the list once. The first id that’s already in the set is the answer.

The waste in Better: nothing, it’s a bug: the counts forget where each copy was. Checking as you go meets the second copies in list order, so the first id found in the set is the first repeat.

It’s the lesson’s duplicate check, giving back the id instead of True.

Highlighted lines are new in this rung.

def first_repeat(ids: list[int]) -> int | None:
    """The first id to show up a second time, or None."""
    seen: set[int] = set()
    for x in ids:
        if x in seen:
            return x
        seen.add(x)
    return None

Time

O(n) on average

Space

O(n)

Why

One look and at most one add for each id.

What changed from the previous rung

from collections import Counter


def first_repeat(ids: list[int]) -> int | None:
    """The first id to show up a second time, or None."""
    counts = Counter(ids)
    seen: set[int] = set()
    for x in ids:
        if counts[x] > 1:
        if x in seen:
            return x
        seen.add(x)
    return None

When Best isn’t best: if you need every repeated id, not just the first, [x for x, c in Counter(ids).items() if c > 1] gives them all, in the order each one first came.

2. The missing ticket (medium)

A show sold tickets numbered 1 to n + 1. At the door, n of them came in, each once, in any order. Write missing_ticket(tickets): the number of the one that didn’t. A big show has 200,000 tickets, so watch time and memory.

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

Hint 1 of 3

Checking each number from 1 up with t not in tickets searches the whole list each time: O(n²).

Hint 2 of 3

A set of the tickets makes each check O(1), but it holds all of them: O(n) memory.

Hint 3 of 3

1 + 2 + … + m is m(m + 1)/2. What’s left when you take away the tickets that came in?

The missing ticket

Ctrl + Enter runs

def missing_ticket(tickets: list[int]) -> int: # Tickets 1 to n + 1 were sold, and these n came in. # Which one is missing? return 0

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

1. ○Not run yet: missing_ticket([4, 1, 5, 2]) → 3
2. ○Not run yet: missing_ticket([2]) → 1
3. ○Not run yet: missing_ticket([1]) → 2
4. ○Not run yet: Extra test
5. ○Not run yet: Speed test: 100,000 tickets, the highest first → 50000
6. ○Not run yet: 200,000 tickets, so which of 1 to 200,001 is missing? In 1 MB → 123457

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

Try your own input

Arguments, separated by commas as in Python

missing_ticket()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check each number in turn

The idea: For t from 1 up, the first t that isn’t in tickets is the answer.

Clear, and it keeps nothing extra.

def missing_ticket(tickets: list[int]) -> int:
    """Tickets 1 to n + 1 were sold, and n came in. Which one is missing?"""
    for t in range(1, len(tickets) + 2):
        if t not in tickets:  # a search through the whole list, for each t
            return t
    raise ValueError("no ticket is missing")

Time

O(n²)

Space

O(1)

Why

Up to n + 1 numbers, each a search through n tickets.

Where it breaks: with 100,000 tickets, billions of comparisons: it runs out of time.

Better

Put the tickets in a set

The idea: back = set(tickets), then the first t that isn’t in back.

The waste in Okay: it searches the same list again for every number. In a set, each check is one look, on average.

Highlighted lines are new in this rung.

def missing_ticket(tickets: list[int]) -> int:
    """Tickets 1 to n + 1 were sold, and n came in. Which one is missing?"""
    back = set(tickets)
    for t in range(1, len(tickets) + 2):
        if t not in back:
            return t
    raise ValueError("no ticket is missing")

Time

O(n) on average

Space

O(n)

Why

n adds to build the set, then up to n + 1 looks.

What changed from the previous rung

def missing_ticket(tickets: list[int]) -> int:
    """Tickets 1 to n + 1 were sold, and n came in. Which one is missing?"""
    back = set(tickets)
    for t in range(1, len(tickets) + 2):
        if t not in tickets:  # a search through the whole list, for each t
        if t not in back:
            return t
    raise ValueError("no ticket is missing")

Where it breaks: memory. The set holds every ticket: megabytes for 200,000, when the answer is one number.

Best

Add them up

The idea: Tickets 1 to m add up to m(m + 1)/2. Take away the sum of the ones that came in, and what’s left is the missing one.

The waste in Better: it remembers every ticket, when only their total matters.

For the example, tickets 1 to 5 add up to 5 × 6 / 2 = 15. The ones that came in add up to 4 + 1 + 5 + 2 = 12, and 15 − 12 = 3.

Highlighted lines are new in this rung.

def missing_ticket(tickets: list[int]) -> int:
    """Tickets 1 to n + 1 were sold, and n came in. Which one is missing?"""
    m = len(tickets) + 1
    # 1 + 2 + ... + m is m(m + 1)/2. Take away what came back.
    return m * (m + 1) // 2 - sum(tickets)

Time

O(n)

Space

O(1)

Why

One pass for sum(), and the formula is one step.

What changed from the previous rung

def missing_ticket(tickets: list[int]) -> int:
    """Tickets 1 to n + 1 were sold, and n came in. Which one is missing?"""
    back = set(tickets)
    for t in range(1, len(tickets) + 2):
        if t not in back:
            return t
    raise ValueError("no ticket is missing")
    m = len(tickets) + 1
    # 1 + 2 + ... + m is m(m + 1)/2. Take away what came back.
    return m * (m + 1) // 2 - sum(tickets)

When Best isn’t best: it needs exactly one ticket missing, and each of the others in once. If a ticket could come in twice, or two could be missing, the sum can’t say which: use the set.

3. The best day to buy (medium)

You have a share’s price for each day, in order. Write best_profit(prices): the most you could make by buying on one day and selling on a later day, or 0 if no later price is higher. Prices are whole numbers, 0 or more. There can be 400,000 days, so watch time and memory.

Example: best_profit([7, 1, 5, 3, 6, 4]) gives 5: buy at 1, sell at 6.

Hint 1 of 3

Trying every buy day with every later sell day is every pair of days: O(n²).

Hint 2 of 3

For each buy day, you only need the highest price after it. A list of those, built from the last day back, makes it O(n). But that list is as long as prices.

Hint 3 of 3

Turn it round: for each sell day, you only need the lowest price before it. That’s one number, which you can keep up to date as you go.

The best day to buy

Ctrl + Enter runs

def best_profit(prices: list[int]) -> int: # The most you can make buying one day and # selling on a later day, or 0. return 0

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

1. ○Not run yet: best_profit([7, 1, 5, 3, 6, 4]) → 5
2. ○Not run yet: best_profit([7, 6, 4, 3, 1]) → 0
3. ○Not run yet: best_profit([2, 4, 1]) → 2
4. ○Not run yet: best_profit([3]) → 0
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 100,000 days, each lower than the day before → 0
7. ○Not run yet: 400,000 days of prices, in 1 MB → 400008

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

Try your own input

Arguments, separated by commas as in Python

best_profit()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Try every pair of days

The idea: For each buy day, try every later sell day, and keep the biggest profit.

It’s the problem, word for word.

def best_profit(prices: list[int]) -> int:
    """The most you can make buying one day and selling on a later day, or 0."""
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):  # every later day
            best = max(best, prices[j] - prices[i])
    return best

Time

O(n²)

Space

O(1)

Why

n(n − 1)/2 pairs of days.

Where it breaks: 100,000 days is about 5 billion pairs: it runs out of time.

Better

The highest price after each day

The idea: Build highest_after from the last day back, then buy on each day and sell at highest_after.

The waste in Okay: for each buy day, it looks through every later day for the highest price, again and again. Going backwards, the highest price after day i is the bigger of day i + 1’s price and the highest after that: one step each.

Highlighted lines are new in this rung.

def best_profit(prices: list[int]) -> int:
    """The most you can make buying one day and selling on a later day, or 0."""
    n = len(prices)
    # highest_after[i]: the highest price on any day after day i.
    highest_after = [0] * n
    for i in range(n - 2, -1, -1):
        highest_after[i] = max(highest_after[i + 1], prices[i + 1])
    best = 0
    for i in range(n - 1):
        best = max(best, highest_after[i] - prices[i])
    return best

Time

O(n)

Space

O(n)

Why

Two passes over the days, and a list as long as prices.

What changed from the previous rung

def best_profit(prices: list[int]) -> int:
    """The most you can make buying one day and selling on a later day, or 0."""
    n = len(prices)
    # highest_after[i]: the highest price on any day after day i.
    highest_after = [0] * n
    for i in range(n - 2, -1, -1):
        highest_after[i] = max(highest_after[i + 1], prices[i + 1])
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):  # every later day
            best = max(best, prices[j] - prices[i])
    for i in range(n - 1):
        best = max(best, highest_after[i] - prices[i])
    return best

Where it breaks: memory. highest_after is as long as prices: megabytes for 400,000 days.

Best

Keep the lowest price so far

The idea: Walk the days once. Selling today, the best buy was the lowest price so far; keep that, and the best profit.

The waste in Better: it keeps a number for every day, when each day only needs one: the lowest price before it. Going forwards, that’s one number to keep up to date.

Highlighted lines are new in this rung.

def best_profit(prices: list[int]) -> int:
    """The most you can make buying one day and selling on a later day, or 0."""
    if not prices:
        return 0
    lowest = prices[0]  # the lowest price so far: the best day to have bought
    best = 0
    for price in prices:
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best

Time

O(n)

Space

O(1)

Why

One pass, and two numbers kept.

What changed from the previous rung

def best_profit(prices: list[int]) -> int:
    """The most you can make buying one day and selling on a later day, or 0."""
    n = len(prices)
    # highest_after[i]: the highest price on any day after day i.
    highest_after = [0] * n
    for i in range(n - 2, -1, -1):
        highest_after[i] = max(highest_after[i + 1], prices[i + 1])
    if not prices:
        return 0
    lowest = prices[0]  # the lowest price so far: the best day to have bought
    best = 0
    for i in range(n - 1):
        best = max(best, highest_after[i] - prices[i])
    for price in prices:
        best = max(best, price - lowest)
        lowest = min(lowest, price)
    return best

When Best isn’t best: it gives the profit, not the days. If you need the days too, keep the day of the lowest price, and the pair of days with the best profit so far: still one pass and O(1) memory.

Check yourself

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

1. Spot the bugThis looks like one loop. What does it cost for n ids, when most are different?

   def unique_ids(ids):
       out = []
       for x in ids:
           if x not in out:
               out.append(x)
       return out

   O(n)O(n log n)O(n²)O(1)

   Check answer
2. Predict the outputHow many pair checks does Okay, the two loops, make here?

   has_duplicate([1, 2, 3, 4, 5, 6])

   6153036

   Check answer
3. Multiple choiceA function takes 3n² + 50n + 1000 steps. What is its Big-O?

   O(3n²)O(n²)O(n² + n)O(n)

   Check answer
4. Multiple choicen can be up to 100,000. Which is the slowest of these that's still likely fast enough in Python?

   O(n²)O(n log n)O(2ⁿ)O(n³)

   Check answer
5. Multiple choiceHow much extra memory does this use, for a list of n numbers (2 or more)?

   def biggest_gap(nums):
       s = sorted(nums)
       return max(s[i] - s[i - 1] for i in range(1, len(s)))

   O(1)O(log n)O(n)O(n²)

   Check answer

Flashcards

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

• Card 1What does Big-O say about a piece of code?Show answer
• Card 2When n doubles, what happens to O(log n), O(n) and O(n²)?Show answer
• Card 3About how big can n be for a second of Python, at O(n log n), O(n²) and O(2ⁿ)?Show answer
• Card 4How many pairs do n items have?Show answer
• Card 5Name some loops hidden in one line of Python.Show answer
• Card 6What counts as a solution's space?Show answer

Add 6 cards to my review deck

Cheat sheet

• Count steps as n grows, not seconds. Keep the part that grows fastest, and drop the number in front of it.
• From fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
• When n doubles: O(log n) takes one more step, O(n) twice the work, O(n²) four times.
• In about a second of Python: up to about a million items for O(n log n), a few thousand for O(n²), about 20 for O(2ⁿ).
• Steps one after another add: O(n + m). Steps inside each other multiply: O(n · m).
• Hidden loops: x in a_list, slices, sorted(), sum(), max(), index() and count().
• Space is the extra memory: count copies, sets and dicts, not the input.
• Big-O means the worst case, unless you say “on average” or “best case”.

Go deeper

• From the Python wiki: the time each list, set and dict operation takes.
• In the Python docs: the Sorting Techniques guide, on sort() and sorted().
• Draw your own: the Counting the work pictures on the DSA visualizer.
• Next on the DSA roadmap: arrays and strings. Two Sum already uses everything here, on a pair that adds up to a target.

Can you do these now?

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

• Count the steps a piece of code takes, and give its Big-O for time and for memory
• Put O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ) in order. Guess how big an input each can handle
• Find a slow step hidden inside a loop, like a slice or x in a list
• Say why Big-O drops the constants, and when they still matter

✓Mark as completeI already know this

Status: Not started