Data structures problem 1 of 30

Contains a duplicate

Data structures
Easy

Write has_duplicate(nums) that returns True if any value appears more than once in the list. Make it O(n).

has_duplicate([1, 2, 3, 1])   # True
has_duplicate([1, 2, 3])      # False

Show hint

A set can tell you in O(1) whether you have seen a value before.

Show solution

def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

Checking every pair would be O(n²). A set makes each lookup O(1) on average, so one pass is enough, and the loop stops at the first repeat. The one-liner len(set(nums)) != len(nums) is also O(n) but always processes the whole list.

Want a problem like this every day? See today's problem and keep a streak going.