Skip to the content
Start

Project: find duplicates fast

Python · Unit 22: Complexity

To know whether a list has duplicates, the slow way compares each number with all the ones ahead of it: with 4 numbers that is 6 comparisons, with 1000 it is almost half a million.

With a set one pass is enough, because asking whether you have seen it is O(1).

nums = [4, 9, 1, 9]
n = len(nums)
steps = 0
for i in range(n):
    for j in range(i + 1, n):
        steps += 1
print(steps)

Prints

6

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Complete the code

    Complete it so the function reports when a number has already shown up before.

  2. 2. Write the code

    Write has_repeat(nums): it returns True if some number shows up twice and False if not. Use a set to remember the ones you have seen, in a single pass.

  3. 3. Write the code

    Now prove it by counting. check(nums) returns a list with two things: whether there is a duplicate, and how many numbers it looked at before answering. Add one step per number you look at and leave as soon as you find the duplicate.

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →