Detecting Duplicates Efficiently

Keep a set of the values you have already seen and check each new value against it before adding it. As soon as a value is found that is already in the set, you have a duplicate and can stop.

def contains_duplicate(values):
    seen = set()
    for value in values:
        if value in seen:
            return True
        seen.add(value)
    return False

print(contains_duplicate([1, 2, 3, 1]))
print(contains_duplicate([1, 2, 3]))

The outputs are True and False. The first array contains 1 twice, and the second contains three distinct values.

The mechanism is the same as everywhere else in this family: a set turns the question of whether a value has been seen into a constant-time hash lookup. Comparing every pair of elements directly would be quadratic, while the set version is linear in the length of the array.

The trade-off to name is space. The set stores one entry per distinct value, so the memory grows with the input. For a duplicate check you do not actually need to store all the values, only the ones you have not yet seen, which is the same thing, so there is no way around the space cost with this approach. The alternative is to sort the data and look for adjacent equal elements, which uses no extra structure beyond what the sort needs but costs O of n log n time. For a large array under a tight memory budget, the sorting approach is the better trade, and for a large array with a generous budget, the set is faster.

Sort the values, then walk the sorted array and compare each element with its predecessor. A duplicate is exactly an adjacent pair of equal values once the data is ordered.

def contains_duplicate_sorted(values):
    values.sort()
    for i in range(1, len(values)):
        if values[i] == values[i - 1]:
            return True
    return False

data = [3, 1, 4, 1, 5, 9, 2, 6]
print(contains_duplicate_sorted(data))
print(data)

The outputs are True and the sorted list 1, 1, 2, 3, 4, 5, 6, 9. The duplicate 1 now sits next to itself, so the adjacent comparison catches it.

The mechanism is that sorting brings equal values together. The check itself is a single linear pass, and the sort is the only expensive part. One detail worth being honest about is that the sort reorders the caller's list, which is visible in the second printed line, so a version that must not mutate its input should sort a copy instead at the price of an extra array.

The trade-off to name is time against space and mutation. The set version is linear in time and linear in space, while the sorting version is n log n in time and uses much less memory, though Python's own sort still allocates some scratch space proportional to the input. If the values fall into a small known range, a boolean array of flags beats both, giving constant time per element and memory proportional to the range. And if the array is already sorted, the adjacent comparison finds a duplicate in linear time with no sort at all.