Contains Duplicate

Approach Summary

Add each element to a Set; return true the moment a duplicate is found.

Full Solution & Approach

The most direct solution: a set can only hold unique values, so if the set built from the array is smaller than the array, at least one value repeated — return len(set(nums)) !== len(nums) in one line. For the more general stream-detect case, iterate and add each value to a set, returning true the moment an add fails because the value already exists. This short-circuits early on the first duplicate instead of scanning everything. The set approach is O(n) time and O(n) space. Sorting first (O(n log n)) and checking adjacent equals uses O(1) space but is slower. The early-exit loop is the version to reach for when the array is large.

Building the set is one pass — O(n) time. The set stores up to n distinct values — O(n) space.

Solution Code

Solution

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

function containsDuplicate(nums) {
  return new Set(nums).size !== nums.length;
}

public boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums) if (!seen.add(n)) return true;
    return false;
}

bool containsDuplicate(const vector<int>& nums) {
    unordered_set<int> seen;
    for (int n : nums) if (!seen.insert(n).second) return true;
    return false;
}

Edge Cases to Watch

Empty or single-element array — no duplicates
All values identical — the first duplicate is found immediately
Negative and zero values — the set handles any type

How to Recognize This Pattern

Existence check across all previous elements
Set is O(1) lookup vs O(n) scan

Complexity Analysis

Time Complexity

O(n)

Space Complexity