Contains Duplicate

Problem Statement

You are given an integer array nums. Return true if at least one value occurs two or more times in the array, and false if every value in the array is distinct.

Examples

Example 1:

Input: nums = [4,7,1,7]
Output: true
Explanation: The value 7 appears at index 1 and at index 3.

Example 2:

Input: nums = [5,-2,9,0]
Output: false
Explanation: All four values are different.

Example 3:

Input: nums = [3,3,3,8,8]
Output: true
Explanation: Both 3 and 8 repeat; one repeat is enough to return true.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Approach 1: Sort and Compare Neighbours

Algorithm

The most literal solution compares every pair (i, j), which costs O(n²) and times out for 10^5 elements. A better simple idea: after sorting, equal values sit next to each other, so a single scan over adjacent pairs finds any duplicate.

1. Sort nums in ascending order.
2. For every index i from 1 to n - 1, compare nums[i] with nums[i - 1].
3. If any adjacent pair is equal, return true.
4. If the scan finishes, return false.

Note that this sorts the input in place. If the caller needs the original order, sort a copy (which costs O(n) extra space).

Implementation

Python:

from typing import List


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()  # equal values become neighbours
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

Java:

import java.util.Arrays;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums); // equal values become neighbours
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

Go:

import "sort"

func containsDuplicate(nums []int) bool {
    sort.Ints(nums) // equal values become neighbours
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            return true
        }
    }
    return false
}

JavaScript:

function containsDuplicate(nums) {
    // Numeric comparator: the default sort compares values as strings
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {
            return true;
        }
    }
    return false;
}

C#:

using System;

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        Array.Sort(nums); // equal values become neighbours
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // equal values become neighbours
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
};

Complexity Analysis

• Time: O(n log n) for the sort; the scan afterwards is O(n).
• Space: O(1) extra beyond the sort itself. The built-in sorts need O(log n) auxiliary memory in C++, Go and C# (introsort/pdqsort) and up to O(n) in Python and JavaScript (Timsort) and in Java, whose Arrays.sort(int[]) can allocate a merge buffer for inputs with long sorted runs.

Approach 2: Hash Set (Optimal)

Algorithm

Walk the array once and remember every value seen so far in a hash set. The first time a value is already in the set, we have found a duplicate and can stop early.

1. Create an empty hash set seen.
2. For each value x in nums:
   • If x is already in seen, return true.
   • Otherwise add x to seen.
3. Return false after the loop.

Several languages let the insert double as the membership test: add/Add/insert report whether the value was new, which saves a second hash lookup.

Implementation

Python:

from typing import List


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for x in nums:
            if x in seen:  # seen before: duplicate found
                return True
            seen.add(x)
        return False

Java:

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            // add() returns false when x was already present
            if (!seen.add(x)) {
                return true;
            }
        }
        return false;
    }
}

Go:

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))
    for _, x := range nums {
        if _, ok := seen[x]; ok { // seen before: duplicate found
            return true
        }
        seen[x] = struct{}{}
    }
    return false
}

JavaScript:

function containsDuplicate(nums) {
    const seen = new Set();
    for (const x of nums) {
        if (seen.has(x)) { // seen before: duplicate found
            return true;
        }
        seen.add(x);
    }
    return false;
}

C#:

using System.Collections.Generic;

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        var seen = new HashSet<int>();
        foreach (int x in nums) {
            // Add() returns false when x was already present
            if (!seen.Add(x)) {
                return true;
            }
        }
        return false;
    }
}

C++:

#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        seen.reserve(nums.size());
        for (int x : nums) {
            // insert(...).second is false when x was already present
            if (!seen.insert(x).second) {
                return true;
            }
        }
        return false;
    }
};

Complexity Analysis

• Time: O(n) on average: one pass with O(1) average-time hash operations.
• Space: O(n) for the set in the worst case, when all values are distinct.

Key Insights

1. The question is about membership. “Have I seen this value before?” is exactly what a hash set answers in O(1) average time.
2. Sorting groups equal values. Once sorted, a duplicate must be adjacent to its twin, so one neighbour check per index is enough.
3. Time versus space. Sorting uses almost no extra memory but costs O(n log n); hashing is O(n) but needs O(n) memory. Interviewers like hearing this trade-off stated plainly.
4. Early exit. Both approaches can stop at the first repeat, which helps a lot when duplicates appear early.

Edge Cases

1. Single element: [42] returns false, because one value cannot repeat.
2. Two equal elements: [6,6] returns true.
3. Negative values and zero: [-1,0,-1] returns true; hashing and sorting both handle negatives.
4. Extreme values: [-1000000000, 1000000000] returns false; nothing is added or multiplied, so there is no overflow risk.
5. All values the same: [2,2,2,2] returns true on the second element in the hash set approach.

Common Mistakes

1. Nested loops in production code. The O(n²) pair check works for tiny inputs but times out at 10^5 elements.
2. Default JavaScript sort. nums.sort() without a comparator orders numbers as strings. It still groups equal values here, but the habit causes real bugs elsewhere, so pass (a, b) => a - b.
3. Starting the neighbour scan at index 0. Comparing nums[0] with nums[-1] reads out of bounds in most languages (and wraps to the last element in Python).
4. Forgetting that sorting mutates the input. Mention it, and sort a copy if the caller still needs the original order.
5. Comparing set size at the end only. len(set(nums)) != len(nums) is correct and short, but it always hashes the whole array; the loop version can stop early.

Interview Tips

1. Lead with the brute force in one sentence, then move straight to the hash set. This problem is a warm-up; the interviewer wants to see you reach O(n) quickly.
2. Ask about memory limits. If extra memory is not allowed, the sort-based solution is the answer, and you should say that it modifies the input.
3. Mention the one-liner (len(set(nums)) < len(nums) in Python) as an aside, but write the explicit loop so the early exit is visible.
4. State average versus worst case. Hash operations are O(1) on average; with adversarial collisions they can degrade, which a sort-based solution avoids.

Follow-up Questions

1. Duplicates within distance k (LC 219): return true only if two equal values are at most k indices apart. Keep a sliding window set of the last k values.
2. Near-duplicates (LC 220): values within t of each other and indices within k. Use buckets of width t + 1 or an ordered set.
3. Find the duplicate without extra space (LC 287): values are in 1..n and the array is read-only, so use Floyd’s cycle detection.
4. Return all duplicated values instead of a boolean: count occurrences in a hash map.
5. Data too large for memory: hash-partition values into files so equal values land in the same file, then check each file separately.

Related Problems

• Two Sum
• Find the Duplicate Number
• Valid Anagram
• Longest Consecutive Sequence
• Group Anagrams