This solved function records where each value was first seen. It is built from exactly the two pieces your answer needs, so read what each one is for.
def first_positions(items):
seen = set()
positions = []
for index, item in enumerate(items):
if item not in seen:
seen.add(item)
positions.append(index)
return positions
# first_positions(['a', 'b', 'a', 'c']) -> [0, 1, 3]
- Two containers, two jobs
The set answers 'have I seen this before?' and the list holds the answer being built. Trying to make one container do both is what produces the slow version below.
- Why a set and not `if item not in positions`
Checking membership in a list scans it from the start, so the check gets slower as the list grows — over n items that is roughly n²/2 comparisons. A set hashes the value and looks in one place, so the check costs the same whether it holds ten items or ten million. On 100,000 items this is the difference between instant and a coffee break.
- Add to seen at the moment you accept
The add and the append happen together, inside the same branch. Split them up and you get the class of bug where a value is recorded as seen but never actually kept.
You need to remember which values have already been output. Which built-in container answers 'is this in here?' quickly, and does not care about order itself?
Keep two things: a set of values you have already taken, and the list you are building. Walk the input once and decide for each item whether it is new.
seen = set(); result = []. For each item in items: if it is not in seen, add it to seen and append it to result. Return result. Note that you never touch items itself.
def dedupe(items): seen = ____() result = [] for item in items: if item not in ____: seen.____(item) result.____(item) return ____
def dedupe(items):
seen = set()
result = []
for item in items:
if item not in seen:
seen.add(item)
result.append(item)
return result
list(dict.fromkeys(items)) does the same job. Dictionary keys are unique and, since Python 3.7, keep insertion order — so a dict is a set that remembers the order it met things. It is the idiomatic short answer, and you should reach for it once you can explain it. Writing the loop first is how you get to that point.
`if item not in result` looks tidier — one container instead of two — and is correct. It is also quadratic: every check rescans everything kept so far. Nobody notices on 50 items; on 50,000 it is the reason a job that should take a second takes minutes. Correct and slow is still a bug when the input grows.
Sets need to hash their members, so this refuses lists and dicts with TypeError. If you genuinely must dedupe unhashable values, either convert them to something hashable for comparison — a tuple, a JSON string — or accept the quadratic scan deliberately, knowing what it costs.
Every version below is correct and verified against the same cases by the build. They are here because knowing which one to reach for is the part that takes judgement, and the trade-off is stated rather than left for you to guess.
def dedupe(items):
return list(dict.fromkeys(items))Reach for this once you can explain it: dict keys are unique and, since 3.7, keep insertion order — so a dict is a set that remembers. Same complexity, one line, and it is what a reviewer expects to see.
def dedupe(items):
result = []
for item in items:
if item not in result:
result.append(item)
return resultCorrect, tidier-looking, and quadratic — every check rescans everything kept so far. Invisible on 50 items, minutes on 50,000. It is also the only version here that works on unhashable items, so it is a real trade rather than simply wrong.
If you do not actually need the order, say so by using set(items) — it is faster, shorter, and tells the reader that order carries no meaning here. Reach for this function only when first-seen order is part of the answer. And if the values are already sorted, itertools.groupby or a simple comparison with the previous item does the job without a set at all.
- Add a `key` parameter so records can be deduplicated by one field — dedupe(users, key=lambda u: u['email']) — while still returning the whole record.
- Make it lazy with yield so it can dedupe a stream that does not fit in memory, and notice which of the two containers still has to grow.
- Write a version that handles unhashable items, measure it against this one on 50,000 values, and decide for yourself where the crossover is.