Contains Duplicate

Interview Prep

Warm-upArrays & Hashingarrayshashset

The problem

Given an integer array, return True if any value appears at least twice, and False if every element is distinct.

Pattern: hashset as a presence detector

"Have I seen this before?" is a hashset's native language. Walk the array once. Ask the set. If yes, done. If not, remember it.

Brute force

def contains_duplicate(nums: list[int]) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

O(n²) time, O(1) space. Correct, but never propose this without a follow-up — the interviewer is waiting for the linear version.

Optimal

def contains_duplicate(nums: list[int]) -> bool:
    seen: set[int] = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

O(n) time, O(n) space. Single pass with early exit on the first hit, so the average case is well below n.

One-liner

def contains_duplicate(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))

Pythonic, correct, but slightly wasteful — it always processes the whole array even when the first duplicate sits at index 1. The explicit-loop version is what you'd write on a whiteboard.

Edge cases

Related