My sort is right, but 50,000 scores take half a minute

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

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. Two loops one inside the other are O(n²): twice the items, four times the work. O(log n) means each step halves what’s left, so a million items take about 20 steps. The full lesson: My code passed every test, then timed out on the big one.

Quick recapRecursion in two minutes· 2 min

A recursive function calls itself on a smaller piece. It needs a base case, small enough to answer at once, and a step that gets smaller every time. Each call waits for the calls it makes. Draw the calls as a tree: the boxes are the time, and the height is the calls in progress at once. The full lesson: My power function crashes when n is 5,000.

def total(nums):
    if not nums:        # base case
        return 0
    return nums[0] + total(nums[1:])   # a smaller piece

See the problem

The interview task: sort a list of scores, lowest first, without sorted(). You do what you’d do with cards: find the smallest, put it first, and repeat with the rest.

def sort_scores(scores):
    for i in range(len(scores)):
        smallest = i
        for j in range(i + 1, len(scores)):
            if scores[j] < scores[smallest]:
                smallest = j
        scores[i], scores[smallest] = scores[smallest], scores[i]
    return scores

Ten scores come back sorted at once. Then the interviewer tries 50,000, and nothing comes back for half a minute. sorted() takes a few thousandths of a second.

Every pass reads all of the rest to find its smallest. 50,000 scores make about 1.25 billion comparisons, even when they were already sorted.

Define the task

Write sort_scores(scores).

• Input: a list of up to 50,000 whole numbers. It can be empty, and can have repeats.
• Output: the same scores, lowest first. You can sort the list you’re given, or return a new one.
• The hard part: don’t use sorted(), .sort() or an import. It must be fast for 50,000 scores in any order.

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

Pause and think

⏸ Pause and think

Before you write any code: you have two piles of cards, each already sorted. How would you make one sorted pile, and how many cards do you need to look at?

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

Hints open one at a time:

Hint 1 of 3

Look at the top card of each pile. The smaller one is the smallest of all, so it goes first. Repeat.

Hint 2 of 3

Each look places one card, so two sorted piles of n cards in all take at most n − 1 looks: one pass.

Hint 3 of 3

Split the list in half, sort each half with a call to your own function, then merge the two halves. A list of one score is already sorted.

Understand the idea

A sort compares two scores at a time. Every sort in this lesson asks one question again and again: is this score smaller than that one? Count the comparisons, and you have the time.

Selection sort compares every pair. Pass 1 compares the other n − 1 scores with the smallest so far, pass 2 the other n − 2, and so on: n(n − 1)/2, about n²/2. The order makes no difference: a sorted list costs just as much.

Watch it. The panel counts the comparisons. Try your own scores, then try them already in order.

Find the smallest, swap it to the front

⤢ Full view

1. 50
2. 21
3. 42
4. 63
5. 14
6. 35

Work so far

smallest so far	none yet
comparisons	0

Step 1 of 28. Find the smallest score, and swap it to the front. Then find the smallest of the rest, and so on. Question: With 6 scores, how many comparisons will it make?

What happens next? With 6 scores, how many comparisons will it make?

51536Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def sort_scores(scores: list[int]) -> list[int]:
2    for i in range(len(scores)):
3        smallest = i
4        for j in range(i + 1, len(scores)):
5            if scores[j] < scores[smallest]:
6                smallest = j
7        scores[i], scores[smallest] = scores[smallest], scores[i]
8    return scores

Try your own input

ScoresShow it

Insertion sort stops early. Take each score in turn, and move it left past every bigger score. A score already in place costs one comparison, so a list in order takes n − 1, and a list nearly in order not many more. A list in reverse is its worst: every score moves all the way, about n²/2 again.

Two sorted lists merge in one pass. Compare their fronts, and take the smaller: it’s the smallest of everything left. Repeat. Each comparison places one score, so n scores take at most n − 1 comparisons.

Merge sort: split, sort each half, merge. A list of 0 or 1 scores is sorted already: that’s the base case. Any other list splits in half, sorts each half with a call, and merges them. Halving gives about log₂ n rows of calls, and the merges on each row read every score once: about n × log₂ n comparisons. For 50,000 scores, that’s under 800,000 instead of 1.25 billion.

That’s as fast as comparing gets. A sort that only compares two scores at a time can’t beat about n log₂ n in the worst case. Sorts that beat it don’t compare: counting how many of each score there are works when the scores are small whole numbers.

A stable sort keeps ties in order. When two items compare equal, a stable sort leaves them in the order they came. That matters when you sort records by one field, like orders by day. Insertion sort and merge sort are stable. Selection sort isn’t: its swap can jump an item past an equal one.

Python’s sorted() and list.sort() are a stable merge sort, in C. It’s called Timsort. It finds runs that are already in order, uses insertion sort on short pieces, and merges the rest: O(n log n) at worst, O(n) on a list in order. key= sorts by what a function gives, like key=len, and reverse=True puts the biggest first. sorted() makes a new list; .sort() changes the list and returns None.

Sorting first can make a problem easy. In a sorted list, equal items sit next to each other, the closest values are neighbours, and two pointers or binary search work. It costs O(n log n), more than a set’s O(n), but needs no hashing, and .sort() needs little extra memory. The practice problems use it.

★Sorting costs n log n, and buys you order

Once a list is sorted, equal items are neighbours, the smallest is first, and you can walk it with two pointers. Many problems get easy after one sorted(). Compare that n log n with what the problem costs without it.

Climb the ladder

All three sort [5, 2, 4, 6, 1, 3]. What changes is how many comparisons they make, and for which lists.

Okay

Find the smallest, swap it to the front

The idea: Find the smallest score, and swap it into index 0. Then find the smallest of the rest, and swap it into index 1, and so on.

It’s how many people sort by hand, and it makes at most n swaps.

def sort_scores(scores: list[int]) -> list[int]:
    for i in range(len(scores)):
        smallest = i
        for j in range(i + 1, len(scores)):
            if scores[j] < scores[smallest]:
                smallest = j
        scores[i], scores[smallest] = scores[smallest], scores[i]
    return scores

Time

O(n²)

Space

O(1)

Why

Pass 1 compares n − 1 scores, pass 2 n − 2, and so on: n(n − 1)/2 comparisons, whatever the order. It only swaps inside the list.

Where it breaks: every pass reads all of the rest, even when the scores are already in order. 50,000 scores take about 1.25 billion comparisons, so it runs out of time even on the list that’s nearly in order.

Better

Move each score left until it fits

The idea: Take each score in turn, and swap it left past every bigger score before it. The scores on its left are always sorted.

The waste in Okay: it reads all of the rest even when there’s nothing to move. Insertion sort stops each score as soon as it fits, so a list in order takes just n − 1 comparisons.

Move each score left until it fits

⤢ Full view

1. 50sorted
2. 21
3. 42
4. 63
5. 14
6. 35

Step 1 of 21. One number on its own is already sorted. Each next number moves left until it fits.

◀ BackPlayNext ▶Reset Ask me first Show as text

1def sort_scores(scores: list[int]) -> list[int]:
2    for i in range(1, len(scores)):
3        j = i
4        while j > 0 and scores[j - 1] > scores[j]:
5            scores[j - 1], scores[j] = scores[j], scores[j - 1]
6            j -= 1
7    return scores

Try your own input

NumbersShow it

Highlighted lines are new in this rung.

def sort_scores(scores: list[int]) -> list[int]:
    for i in range(1, len(scores)):
        j = i
        while j > 0 and scores[j - 1] > scores[j]:
            scores[j - 1], scores[j] = scores[j], scores[j - 1]
            j -= 1
    return scores

Time

O(n²)

Space

O(1)

Why

A score already in place costs one comparison, so a list nearly in order takes about n. In the worst case, a list in reverse, each score moves all the way left: n(n − 1)/2 swaps.

What changed from the previous rung

def sort_scores(scores: list[int]) -> list[int]:
    for i in range(len(scores)):
        smallest = i
        for j in range(i + 1, len(scores)):
            if scores[j] < scores[smallest]:
                smallest = j
        scores[i], scores[smallest] = scores[smallest], scores[i]
    for i in range(1, len(scores)):
        j = i
        while j > 0 and scores[j - 1] > scores[j]:
            scores[j - 1], scores[j] = scores[j], scores[j - 1]
            j -= 1
    return scores

Where it breaks: a mixed order. Each score moves about halfway left, so 50,000 scores take about 625 million swaps: it runs out of time on the mixed speed test.

Best

Split in half, sort each half, merge

The idea: A list of 0 or 1 scores is sorted. Any other list splits in half, sorts each half with a call, and merges them: compare the two fronts, take the smaller, repeat.

The waste in Better: a swap moves a score just one place, so a score far from home takes many swaps. A merge puts each score straight into its place in the merged list, and each score is merged only about log₂ n times.

Split in half, sort each half, merge

⤢ Full view

Calls so far, each under the call that made it:

• sort_scores([5, 2, 4, 6, 1, 3]): running now

Work so far

calls made	1
comparisons so far	0

• Running now
• Waiting for a call it made
• Done: shows what it returned

Step 1 of 22. sort_scores([5, 2, 4, 6, 1, 3]) splits at index 3: [5, 2, 4] and [6, 1, 3]. It sorts the left half with a call, and waits. Question: With 6 scores, how many rows will the tree of calls have?

What happens next? With 6 scores, how many rows will the tree of calls have?

346Just show me

◀ BackPlayNext ▶Reset Ask me first Show as text

1def sort_scores(scores: list[int]) -> list[int]:
2    if len(scores) <= 1:
3        return scores
4    middle = len(scores) // 2
5    left = sort_scores(scores[:middle])
6    right = sort_scores(scores[middle:])
7    return merge(left, right)
8 
10def merge(left: list[int], right: list[int]) -> list[int]:
11    merged = []
12    i = j = 0
13    while i < len(left) and j < len(right):
14        if left[i] <= right[j]:  # <= keeps equal scores in their order
15            merged.append(left[i])
16            i += 1
17        else:
18            merged.append(right[j])
19            j += 1
20    return merged + left[i:] + right[j:]

Try your own input

ScoresShow it

Highlighted lines are new in this rung.

def sort_scores(scores: list[int]) -> list[int]:
    if len(scores) <= 1:
        return scores
    middle = len(scores) // 2
    left = sort_scores(scores[:middle])
    right = sort_scores(scores[middle:])
    return merge(left, right)


def merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps equal scores in their order
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

Time

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

Space

O(n)was O(1)

Why

Halving gives about log₂ n rows of calls, and the merges on each row read every score once: about n × log₂ n. The halves and merged lists hold about n scores at a time.

What changed from the previous rung

def sort_scores(scores: list[int]) -> list[int]:
    for i in range(1, len(scores)):
        j = i
        while j > 0 and scores[j - 1] > scores[j]:
            scores[j - 1], scores[j] = scores[j], scores[j - 1]
            j -= 1
    return scores
    if len(scores) <= 1:
        return scores
    middle = len(scores) // 2
    left = sort_scores(scores[:middle])
    right = sort_scores(scores[middle:])
    return merge(left, right)


def merge(left: list[int], right: list[int]) -> list[int]:
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps equal scores in their order
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

When Best isn’t best: in real code, write sorted(scores). It’s the same idea, plus insertion sort on short runs, written in C: many times faster. And when the scores are small whole numbers, like 0 to 100, count how many of each there are. That takes O(n + 101), faster than any sort that compares.

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 first speed test, even though that list is nearly in order. Better passes it, but runs out of time on the mixed one.

Sort the scores

Ctrl + Enter runs

def sort_scores(scores: list[int]) -> list[int]: # Return the scores, lowest first, # without sorted(), .sort() or an import. return scores

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

1. ○Not run yet: sort_scores([5, 2, 4, 6, 1, 3]) → [1, 2, 3, 4, 5, 6]
2. ○Not run yet: sort_scores([3, 1, 3, 2, 1]) → [1, 1, 2, 3, 3]
3. ○Not run yet: sort_scores([]) → []
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Speed test: 50,000 scores nearly in order, each pair swapped: 1, 0, 3, 2, …
8. ○Not run yet: Speed test: 50,000 scores in a mixed order

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

Try your own input

Arguments, separated by commas as in Python

sort_scores()Run onceVisualize

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: selection sort	O(n²), always	O(1)	Simple; at most n swaps	n²/2 comparisons, even on a sorted list	A tiny list
Better: insertion sort	O(n²); O(n) nearly in order	O(1)	Quick on a list nearly in order; stable	About n²/4 swaps on a mixed list, and a swap costs more than a comparison	A short list, or one nearly in order
Best: merge sort	O(n log n), always	O(n)	Fast for any order; stable	Extra memory for the halves	A big list in an interview; sorted() in real code

How much work is that? Each bar is one rung, for n scores in a mixed order. Pick a size, or run the race.

Sorting n scores in a mixed order: comparisons

1. OkayFind the smallest, swap it · O(n²)≈ 1,200,000,000 comparisons

2. BetterMove each score left · O(n²)≈ 620,000,000 comparisons

3. BestSplit, sort, merge · O(n log n)≈ 780,000 comparisons

At n = 50,000, Okay does about 1,600 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 is for a mixed order. On a list nearly in order, insertion sort drops to about n, and selection sort stays at n²/2.

The race also gives every step the same time, but real steps differ. Each of insertion sort’s steps is a swap, which costs more than selection sort’s comparison. So in Python, insertion sort is slower on a mixed list: 20,000 scores take about 5 seconds with selection sort, and 7 or more with insertion sort. Insertion sort wins when the list is nearly in order.

Common mistakes and edge cases

!list.sort() returns None

scores = scores.sort() sorts the list, then sets scores to None, because .sort() changes the list and returns nothing. Write scores.sort() on its own line, or scores = sorted(scores) for a new list.

• Merge with <=, not <. On a tie, <= takes the score from the left half first, so equal items keep their order. With < the sort still works, but isn’t stable.
• Strings sort by character code. 'Zoe' comes before 'adam', because capitals come first, and '10' before '9'. Use key=str.lower, or key=int for numbers kept as text.
• Mixed types don’t sort. sorted([3, '2']) raises TypeError: Python won’t compare a number with a string.
• Sort by two things with a tuple. key=lambda o: (o.day, -o.total) sorts by day, then the biggest total first. Or sort twice, the less important key first: the sort is stable, so the second sort keeps the first one’s order inside ties.
• Slices copy, and pop(0) is slow. scores[:middle] makes a new list, which is fine for merge sort’s O(n) memory. But taking the front of a list with pop(0) moves every item after it, O(n) each time: walk with an index instead.

Say it in the interview

Questions to ask first

• How many items, and are they nearly in order already?
• Are the values small whole numbers? Then counting can beat any comparing sort.
• Must equal items keep their order?
• Sort in place, or return a new list? How much extra memory can it use?

A 60-second walkthrough

“I’ll use merge sort. A list of 0 or 1 items is already sorted. Otherwise I split it in half, sort each half with a recursive call, and merge the two sorted halves: compare the fronts, take the smaller, and when one runs out, add the rest of the other. Halving gives about log₂ n levels, and each level’s merges touch every item once, so it’s O(n log n) time, for any order. It uses O(n) extra memory for the halves, and only about log₂ n calls are in progress at once, so no recursion limit problem. On a tie I take from the left half, so it’s stable. In real code I’d call sorted(), which is a stable merge sort in C.”

Likely follow-ups

• What about quicksort? Pick a pivot, put smaller items to its left and bigger to its right, then sort each side. It’s O(n log n) on average and in place. But it’s O(n²) when the pivots are bad, like always taking the first item of a sorted list. A random pivot makes that very unlikely.
• Can you sort in place, with O(1) extra memory, in O(n log n)? Heap sort does: it’s in the heaps lesson. It isn’t stable.
• Why does Python’s sort keep ties in order? So you can sort by one field, then another, and keep both orders: sort by the less important key first.
• Scores from 0 to 100? Count how many of each, then write them out in order: O(n + 101) time, with no comparisons.

Practice

Three problems, from easy to medium: sorting by one field, then two problems that sorting first makes easy. 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. Sort orders by day (easy)

Write sort_by_day(orders). Each order is a pair [day, id]. Return the orders sorted by day, and keep orders on the same day in the order they came.

Example: sort_by_day([[3, 'c1'], [1, 'a9'], [3, 'b2'], [2, 'z5']]) gives [[1, 'a9'], [2, 'z5'], [3, 'c1'], [3, 'b2']]. Plain sorted(orders) puts [3, 'b2'] first of the two on day 3: it compares the ids too.

Hint 1 of 3

Sorting the pairs compares the ids when the days are equal. Sort by the day alone.

Hint 2 of 3

A stable sort never swaps two orders whose days are equal. Insertion sort with > is stable; selection sort’s long swaps aren’t.

Hint 3 of 3

sorted() takes key=, a function that gives what to sort by, and Python’s sort is stable.

Sort orders by day

Ctrl + Enter runs

def sort_by_day(orders: list[list]) -> list[list]: # Each order is [day, id]. Sort by day, and keep # orders on the same day in the order they came. return orders

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

1. ○Not run yet: sort_by_day([[3, 'c1'], [1, 'a9'], [3, 'b2'], [2, 'z5']]) → [[1, 'a9'], [2, 'z5'], [3, 'c1'], [3, 'b2']]
2. ○Not run yet: sort_by_day([]) → []
3. ○Not run yet: All on one day: they keep their order → [[5, 'x'], [5, 'a'], [5, 'm']]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: 20,000 orders over 30 days

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

Try your own input

Arguments, separated by commas as in Python

sort_by_day()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Selection sort, by day

The idea: Find the order with the smallest day, and swap it to the front. Repeat with the rest.

It sorts by the day alone, so it never compares the ids.

def sort_by_day(orders: list[list]) -> list[list]:
    for i in range(len(orders)):
        first = i
        for j in range(i + 1, len(orders)):
            if orders[j][0] < orders[first][0]:
                first = j
        orders[i], orders[first] = orders[first], orders[i]  # can jump an order past one on its day
    return orders

Time

O(n²)

Space

O(1)

Why

Each pass reads all of the rest: n(n − 1)/2 comparisons.

Where it breaks: a swap can jump an order past another on the same day. In the example, the second pass swaps z5 forward and sends c1 to the end, behind b2: the wrong order. And 20,000 orders run out of time.

Better

Insertion sort, by day

The idea: Move each order left past every order with a bigger day. Stop at an equal day, so equal days never pass each other.

The waste in Okay: its long swaps break ties. Insertion sort only swaps neighbours, and only when the day before is bigger, so it’s stable.

Highlighted lines are new in this rung.

def sort_by_day(orders: list[list]) -> list[list]:
    for i in range(1, len(orders)):
        j = i
        while j > 0 and orders[j - 1][0] > orders[j][0]:  # > not >=: equal days never swap
            orders[j - 1], orders[j] = orders[j], orders[j - 1]
            j -= 1
    return orders

Time

O(n²)

Space

O(1)

Why

Each order moves left past the orders with bigger days before it: about n²/4 swaps for a mixed order.

What changed from the previous rung

def sort_by_day(orders: list[list]) -> list[list]:
    for i in range(len(orders)):
        first = i
        for j in range(i + 1, len(orders)):
            if orders[j][0] < orders[first][0]:
                first = j
        orders[i], orders[first] = orders[first], orders[i]  # can jump an order past one on its day
    for i in range(1, len(orders)):
        j = i
        while j > 0 and orders[j - 1][0] > orders[j][0]:  # > not >=: equal days never swap
            orders[j - 1], orders[j] = orders[j], orders[j - 1]
            j -= 1
    return orders

Where it breaks: 20,000 orders in a mixed order take about 100 million swaps: it runs out of time.

Best

sorted() with key=

The idea: sorted(orders, key=lambda order: order[0]) sorts by the day alone. Python’s sort is stable, so equal days keep their order.

The waste in Better: each swap moves an order one place. Python’s sort is a stable merge sort in C, and key= tells it to compare the days alone.

Highlighted lines are new in this rung.

def sort_by_day(orders: list[list]) -> list[list]:
    # Sort by the day alone. Python's sort keeps orders on the same day in their order.
    return sorted(orders, key=lambda order: order[0])

Time

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

Space

O(n)was O(1)

Why

Python’s sort is a merge sort: n log n comparisons, and a new list of n orders.

What changed from the previous rung

def sort_by_day(orders: list[list]) -> list[list]:
    for i in range(1, len(orders)):
        j = i
        while j > 0 and orders[j - 1][0] > orders[j][0]:  # > not >=: equal days never swap
            orders[j - 1], orders[j] = orders[j], orders[j - 1]
            j -= 1
    return orders
    # Sort by the day alone. Python's sort keeps orders on the same day in their order.
    return sorted(orders, key=lambda order: order[0])

When Best isn’t best: with only a few days, like 30, you could put each order in a list for its day and then join the lists: O(n + d) for d days, and stable too. sorted() is simpler, and fast enough.

2. Ids in both lists (easy)

Write in_both(a, b): the ids that are in both lists, smallest first, each once.

Example: in_both([4, 9, 5], [9, 4, 9, 8, 4]) gives [4, 9].

Hint 1 of 3

x in b reads b from the start, so checking every id of a that way is O(n · m).

Hint 2 of 3

Sort both lists, then walk them with two pointers. If one id is smaller, it can’t be in the other list further on, so move past it. If they match, you’ve found one.

Hint 3 of 3

Or make a set of each list: set(a) & set(b) holds the ids in both. Then sort just those.

Ids in both lists

Ctrl + Enter runs

def in_both(a: list[int], b: list[int]) -> list[int]: # The ids in both a and b, smallest first, each once. return []

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

1. ○Not run yet: in_both([4, 9, 5], [9, 4, 9, 8, 4]) → [4, 9]
2. ○Not run yet: in_both([1, 2, 3], [4, 5]) → []
3. ○Not run yet: in_both([], [1]) → []
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Speed test: two lists of 50,000 ids

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

Try your own input

Arguments, separated by commas as in Python

in_both()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check each id with in

The idea: For each id in a, check whether it’s in b and not found yet. Sort what you found.

Short, and reads like the question.

def in_both(a: list[int], b: list[int]) -> list[int]:
    found = []
    for x in a:
        if x in b and x not in found:  # each `in` reads a list from the start
            found.append(x)
    found.sort()
    return found

Time

O(n · m)

Space

O(k)

Why

Each of the n ids in a reads b, m ids long. found holds the k ids in both.

Where it breaks: two lists of 50,000 ids take up to 2.5 billion reads: it runs out of time.

Better

Sort both, then walk them together

The idea: Sort a and b. Walk both with two pointers: move past the smaller id, and when the two match, keep it once and move both.

The waste in Okay: x in b reads b from the start for every id. Once both lists are sorted, an id smaller than the other list’s current one can’t be further on, so one walk finds every match.

Highlighted lines are new in this rung.

def in_both(a: list[int], b: list[int]) -> list[int]:
    a = sorted(a)
    b = sorted(b)
    found = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            if not found or found[-1] != a[i]:  # skip repeats
                found.append(a[i])
            i += 1
            j += 1
    return found

Time

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

Space

O(n + m)was O(k)

Why

Sorting costs n log n and m log m. Then the walk reads each id once. The sorted copies hold n + m ids.

What changed from the previous rung

def in_both(a: list[int], b: list[int]) -> list[int]:
    a = sorted(a)
    b = sorted(b)
    found = []
    for x in a:
        if x in b and x not in found:  # each `in` reads a list from the start
            found.append(x)
    found.sort()
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            if not found or found[-1] != a[i]:  # skip repeats
                found.append(a[i])
            i += 1
            j += 1
    return found

Not so good: the sorting is the slow part, more than the O(n + m) that sets need. But if both lists come sorted already, the walk alone is O(n + m), with no extra memory.

Best

Make two sets, keep the ids in both

The idea: set(a) & set(b) holds the ids in both lists, each once. Sort just those.

The waste in Better: it sorts all n + m ids to find the few in both. Sets find each match in O(1) on average, so only the k matches need sorting.

Highlighted lines are new in this rung.

def in_both(a: list[int], b: list[int]) -> list[int]:
    return sorted(set(a) & set(b))

Time

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

Space

O(n + m)

Why

Making the sets reads each id once, and & checks each id of one set in the other in O(1) on average. Only the k ids in both get sorted.

What changed from the previous rung

def in_both(a: list[int], b: list[int]) -> list[int]:
    a = sorted(a)
    b = sorted(b)
    found = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            if not found or found[-1] != a[i]:  # skip repeats
                found.append(a[i])
            i += 1
            j += 1
    return found
    return sorted(set(a) & set(b))

When Best isn’t best: items that can’t go in a set, like lists, need the sort. And when both lists are already sorted, Better’s walk is O(n + m) with no extra memory.

3. H-index (medium)

Write h_index(citations). citations[i] is how many times paper i was cited. The h-index is the biggest h such that h of the papers have at least h citations each.

Example: h_index([3, 0, 6, 1, 5]) gives 3. Three papers, with 3, 6 and 5 citations, have at least 3 each, but there aren’t four with at least 4.

Hint 1 of 3

Try each h from the biggest it could be, the number of papers, down. Count the papers with at least h citations. That count is O(n) for each h.

Hint 2 of 3

Sort the counts, biggest first. Then h papers have at least h citations exactly when the paper ranked h does.

Hint 3 of 3

h can’t be more than n, so a paper with more than n citations counts as n. Count how many papers have each number, then add up from n down until the total reaches h.

H-index

Ctrl + Enter runs

def h_index(citations: list[int]) -> int: # The biggest h such that h papers have # at least h citations each. return 0

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

1. ○Not run yet: h_index([3, 0, 6, 1, 5]) → 3
2. ○Not run yet: h_index([1, 3, 1]) → 1
3. ○Not run yet: h_index([]) → 0
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Extra test
8. ○Not run yet: Speed test: 100,000 papers, with 0 to 999 citations each → 990

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

Try your own input

Arguments, separated by commas as in Python

h_index()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Try every h, from n down

The idea: For each h from n down to 1, count the papers with at least h citations. Return the first h whose count is at least h.

It follows the definition word for word, so it’s easy to trust.

def h_index(citations: list[int]) -> int:
    for h in range(len(citations), 0, -1):
        at_least_h = sum(1 for c in citations if c >= h)  # reads every paper again
        if at_least_h >= h:
            return h
    return 0

Time

O(n²)

Space

O(1)

Why

Each h tried reads all n papers, and it can try up to n values of h.

Where it breaks: with 100,000 papers and an answer of 990, it tries 99,000 values of h, each reading 100,000 papers: about 10 billion reads. It runs out of time.

Better

Sort, biggest first, and walk

The idea: Sort the counts, biggest first. Walk down while the paper ranked h + 1 has more than h citations. Where it stops is h.

The waste in Okay: it counts the same papers again for every h. Sorted biggest first, the paper ranked h is the one that decides whether h works, so one walk finds h.

Highlighted lines are new in this rung.

def h_index(citations: list[int]) -> int:
    ranked = sorted(citations, reverse=True)
    h = 0
    while h < len(ranked) and ranked[h] > h:
        h += 1  # the paper ranked h + 1 has at least h + 1 citations
    return h

Time

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

Space

O(n)was O(1)

Why

The sort is n log n. Then the walk reads each paper at most once. The sorted copy holds n counts.

What changed from the previous rung

def h_index(citations: list[int]) -> int:
    for h in range(len(citations), 0, -1):
        at_least_h = sum(1 for c in citations if c >= h)  # reads every paper again
        if at_least_h >= h:
            return h
    return 0
    ranked = sorted(citations, reverse=True)
    h = 0
    while h < len(ranked) and ranked[h] > h:
        h += 1  # the paper ranked h + 1 has at least h + 1 citations
    return h

Not so good: the sort is the slow part, O(n log n), and it orders big counts that never matter: no answer is bigger than n.

Best

Count the papers, capped at n

The idea: Count how many papers have each number of citations, counting anything above n as n. Add up from n down: the first h where the total reaches h is the answer.

The waste in Better: it sorts counts it doesn’t need in order: a paper with 5,000 citations counts the same as one with n. Capped at n, a list of n + 1 counts takes the place of the sort. That’s counting sort, and it doesn’t compare at all.

Highlighted lines are new in this rung.

def h_index(citations: list[int]) -> int:
    n = len(citations)
    papers = [0] * (n + 1)  # papers[c]: how many have c citations, with n for n or more
    for c in citations:
        papers[min(c, n)] += 1
    at_least = 0
    for h in range(n, 0, -1):
        at_least += papers[h]  # papers with h or more citations
        if at_least >= h:
            return h
    return 0

Time

O(n)was O(n log n)

Space

O(n)

Why

One pass to count, and one pass down from n. The counts list has n + 1 places.

What changed from the previous rung

def h_index(citations: list[int]) -> int:
    ranked = sorted(citations, reverse=True)
    h = 0
    while h < len(ranked) and ranked[h] > h:
        h += 1  # the paper ranked h + 1 has at least h + 1 citations
    return h
    n = len(citations)
    papers = [0] * (n + 1)  # papers[c]: how many have c citations, with n for n or more
    for c in citations:
        papers[min(c, n)] += 1
    at_least = 0
    for h in range(n, 0, -1):
        at_least += papers[h]  # papers with h or more citations
        if at_least >= h:
            return h
    return 0

When Best isn’t best: for a short list, Better is simpler to explain, and both are quick.

Check yourself

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

1. Multiple choiceA list of 10,000 scores is already sorted. Which sort makes the fewest comparisons on it?

   Selection sortInsertion sortMerge sortThey all make the same number

   Check answer
2. Predict the outputWhat does this print?

   scores = [3, 1, 2]
   scores = scores.sort()
   print(scores)

   [1, 2, 3][3, 1, 2]NoneTypeError

   Check answer
3. Spot the bugThis merges two sorted lists for a stable merge sort. What's wrong?

   def merge(left, right):
       merged = []
       i = j = 0
       while i < len(left) and j < len(right):
           if left[i] < right[j]:
               merged.append(left[i])
               i += 1
           else:
               merged.append(right[j])
               j += 1
       return merged + left[i:] + right[j:]

   It loses the items left over when one list runs outOn a tie it takes from the right, so equal items swap orderIt's O(n²)Nothing

   Check answer
4. Pick the patternYou get a list of meeting times as [start, end] pairs and must say whether any two overlap. What makes this easy?

   Sort by start, then compare each meeting with the next oneA set of the start timesRecursion on the first meeting and the restBinary search for each meeting's end

   Check answer
5. Multiple choiceMerge sort on 1,024 scores. About how many comparisons does it make, at most?

   About 1,000About 10,000About 500,000About 1,000,000

   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 selection sort work, and what does it cost?Show answer
• Card 2When is insertion sort fast?Show answer
• Card 3How does merge sort work?Show answer
• Card 4How do you merge two sorted lists?Show answer
• Card 5What is a stable sort?Show answer
• Card 6sorted(xs) or xs.sort()?Show answer

Add 6 cards to my review deck

Cheat sheet

• Selection sort: find the smallest of the rest, swap it into place. n²/2 comparisons, always. Not stable.
• Insertion sort: move each item left until it fits. O(n²), but O(n) on a list nearly in order. Stable.
• Merge sort: split in half, sort each half, merge. O(n log n) for any order, O(n) extra memory. Stable with <=.
• Merging two sorted lists: compare the fronts, take the smaller. One pass.
• No sort that compares beats n log n in the worst case. Counting beats it for small whole numbers.
• sorted(xs) makes a new list; xs.sort() changes xs and returns None. Both are stable, O(n log n), and O(n) on a sorted list.
• key= sorts by what a function gives; reverse=True puts the biggest first.
• Sorting first puts equal items next to each other and lets two pointers walk the list.

Go deeper

• In the Python docs: the Sorting Techniques guide, on key=, stability and sorting by several fields.
• Step through more: Insertion sort on the DSA visualizer, with a “Do it yourself” round, and Merge sort.
• Two Sum uses a sorted list and two pointers in its practice problems.
• Next on the DSA roadmap: stacks and queues.

Can you do these now?

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

• Say how selection, insertion and merge sort work, and what each costs
• Write merge sort, with a merge that keeps equal items in order
• Use sorted() and list.sort() with key= and reverse=, and know they are stable
• Spot a problem that gets easy once its input is sorted

✓Mark as completeI already know this

Status: Not started