Practice: Analysing a Function That Removes Duplicates

State the time and space of a deduplicating function, then rewrite it to run in linear time.

Analysing a function means counting its loops, the work inside each call and the memory it adds, then fixing what the count shows to be slow. This card covers all of that on one function, which removes repeated items from a list and keeps the first of each.

Each item is kept only if it does not appear earlier in the list:

remove_duplicates.pypy

def remove_duplicates(items: list[int]) -> list[int]:
    result = []
    for i in range(len(items)):
        if items[i] not in items[:i]:
            result.append(items[i])
    return result

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

remove_duplicates([3, 1, 3, 2, 1]) = [3, 1, 2]
remove_duplicates([5, 5, 5]) = [5]
remove_duplicates([]) = []

For a list of n items:

State its time complexity, line by line.
State the extra space it uses.
Rewrite it to run in O(n) time.

Show the answers

Line 4 decides the count, because both items[:i] and not in do work that grows with i. A traced run on [3, 1, 3, 2, 1] counted line 3 six times, line 4 five times and line 5 three times.

Runs of each line of remove_duplicates for a list of n items
Line	Runs	Why
3, the loop's header	n + 1	Once per index, once more to stop
4, the slice and the check	n	Run i copies i items into a new list, then scans up to i of them
5, the append	At most n	Once per item kept

Line 4 copies 0 + 1 + … + (n − 1) = n(n − 1)/2 items in all, and scans up to as many, so the function is O(n²) time. Its extra space is O(n): result holds up to n items, and each slice holds up to n − 1 but is discarded before the next is made.

A set of the items already seen replaces both the slice and the scan with one lookup:

remove_duplicates_set.pypy

def remove_duplicates(items: list[int]) -> list[int]:
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

remove_duplicates([3, 1, 3, 2, 1]) = [3, 1, 2]
remove_duplicates([5, 5, 5]) = [5]
remove_duplicates([]) = []

Each lookup and each add is O(1) expected, so the rewrite is O(n) expected time. seen and result hold up to n items each, so its extra space is still O(n).

← → move through sections and cards