Comparing every pair is slow

Does a list contain the same value twice? The obvious way is to compare each value with every value after it. That's fine for 100 values. For a million, it's about 500 billion comparisons, far too slow.

The trouble is that each new value makes you look back through everything you've seen. What if you could remember what you've seen in a way that answers "have I seen this before?" instantly?

Every pair: about n × n steps: hopeless for big lists.

Walk once, remember as you go

4 isn't in {}. Add it: seen = {4}.

Move 1 of 4

A set remembers what you've seen

A set is exactly that memory. Walk the list once. For each value, ask the set whether it's already there. If it is, you've found a repeat. If not, add it and move on.

Each question takes about one step, so the whole walk takes about n steps instead of n × n. Every language has one: a set in Python, an unordered_set in C++, a HashSet in Java, a Set in JavaScript.

Is it in the set? about one step, however big the set.

In code

seen = set()
for x in nums:
    if x in seen:
        return True
    seen.add(x)
return False