How to Remove Duplicates From a Python List and Keep the Order

The slow version

This function removes duplicate events and keeps the first occurrence of each:

def dedup(events: list[str]) -> list[str]:
    seen = []
    out = []
    for event in events:
        if event not in seen:     # scans the whole list every time
            seen.append(event)
            out.append(event)
    return out

It is correct, and with 100 events it is instant. With 100,000 events it can take minutes. The code did not change - only the input size did.

Why it is slow: O(n^2)

event not in seen on a list compares event with each element, one by one, until it finds a match or reaches the end. As seen grows, every check costs more. For n events with many unique values, the total work grows with n * n:

Events	Comparisons (roughly, all unique)
1,000	500,000
10,000	50,000,000
100,000	5,000,000,000

Ten times more input means about a hundred times more work. That is the pattern to recognise: a loop over the data with a list search inside it.

The fix: use a set for membership

def dedup(events: list[str]) -> list[str]:
    seen = set()
    out = []
    for event in events:
        if event not in seen:     # hash lookup, O(1) on average
            seen.add(event)
            out.append(event)
    return out

A set stores items in a hash table. To check event in seen, Python computes the hash of event and looks in one place, so the cost does not grow with the size of the set. The loop now does a constant amount of work per event: O(n) in total.

The output list out keeps the order, because items are appended in the order they first appear. The set is only used to answer "have I seen this?".

The one-line version: dict.fromkeys

Since Python 3.7, dictionaries keep insertion order. dict.fromkeys builds a dict with each item as a key, and duplicate keys are ignored:

def dedup(events: list[str]) -> list[str]:
    return list(dict.fromkeys(events))

dedup(["a", "b", "a", "c", "b", "d"])
# ['a', 'b', 'c', 'd']

This is also O(n) and is usually the shortest correct answer.

Why not list(set(items))?

list(set(["a", "b", "a", "c"]))
# order is not guaranteed, e.g. ['c', 'a', 'b']

list(set(...)) removes duplicates fast, but a set has no order. If the order of the result does not matter, it is fine. If it does - events, log lines, user choices - use the set-plus-list loop or dict.fromkeys.

Measure before and after

time python3 -c "from dedup import dedup; print(len(dedup([f'e{i%10000}' for i in range(20000)])))"

With the list version this takes seconds. With the set version it prints 10000 almost at once. Also check the edge cases, because a faster function that returns a different result is a new bug:

assert dedup(["a", "b", "a", "c", "b", "d"]) == ["a", "b", "c", "d"]
assert dedup([]) == []
assert dedup(["x"]) == ["x"]

Items that are not hashable

Sets and dict keys need hashable items. Strings, numbers and tuples work. Lists and dicts do not - set().add([1, 2]) raises TypeError: unhashable type: 'list'. To dedup a list of dicts, build a hashable key from the fields that define "the same":

def dedup_records(records):
    seen = set()
    out = []
    for r in records:
        key = (r["user_id"], r["event_type"], r["timestamp"])
        if key not in seen:
            seen.add(key)
            out.append(r)
    return out

The wider lesson

The same problem appears in many forms: if user_id in allowed_ids_list inside a loop, list.index() in a loop, or a nested loop to find matches between two lists. If you search a collection many times, build a set or a dict once and look up in that instead.