Contains Duplicates

Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct. This is LeetCode 217.

Example 1
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: 1 appears twice.
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: all values are different.

How to Think About It

Step 1: Comparing every pair

Two loops comparing every pair work, but take O(n²).

Step 2: Sorting brings copies together

After sorting, equal values sit next to each other, so one pass comparing neighbours finds a repeat. That is O(n log n) and needs no extra memory if sorting in place is allowed.

Step 3: A set remembers what you have seen

Walk through the array and add each value to a HashSet. Set.add returns false when the value is already there, which is exactly the moment a duplicate appears. Stop and return true.

Walkthrough

nums = [1, 2, 3, 1].

ValueAlready in the set?Set after
1no{1}
2no{1, 2}
3no{1, 2, 3}
1yesreturn true

Java Solution

The loop stops at the first repeat, so arrays with an early duplicate finish quickly.

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

public class ContainsDuplicates {

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

    public static void main(String[] args) {
        System.out.println(containsDuplicate(new int[] {1, 2, 3, 1}));   // true
        System.out.println(containsDuplicate(new int[] {1, 2, 3, 4}));   // false
    }
}

The original implementation, ContainsDuplicates.java, is on GitHub.

Complexity

  • Set: O(n) time, O(n) space.
  • Sorting: O(n log n) time, O(1) extra space with an in-place sort.

When the two copies must also be close together, see Contains Duplicate II.