Contains Duplicate

The Problem

Return true if any value appears at least twice in the array, and false if every element is distinct.

The Idea

A hash set answers "have I seen this before?" in O(1). Walk the array once; the moment we try to add a value that's already there, we've found a duplicate.

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

• Time: O(n)
• Space: O(n)

Even Shorter

If the array has duplicates, the set will be smaller than the list:

def contains_duplicate(nums):
    return len(set(nums)) < len(nums)

Clean, but in an interview, walk through the explicit loop first so you can talk about the early exit.

Kernel Queen tip: "Have I seen this?" → reach for a set. "How many times have I seen this?" → reach for a hash map (dictionary).