Contains Duplicate

Return true if any value appears at least twice. Add each value to a hash set; add returns false the moment a value is already there.

Traced input: nums = [1, 2, 3, 1] → true. Original problem: neetcode.io/problems/duplicate-integer

Complexity

Best case is a duplicate in the first two elements. The set can hold all n values.

Key idea

• A HashSet answers "seen before?" in O(1).
• set.add(x) returns false if x was already present, so check and insert in one call.
• Stop at the first duplicate; no need to finish the scan.

Common mistakes

• Sorting and comparing neighbours is O(n log n) and mutates the input.
• Comparing every pair is O(n²) and times out.

Solution

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (!seen.add(nums[i])) {
            return true;
        }
    }
    return false;
}

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

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

Edge cases

Each one has its own trace in the interactive view.