Contains Duplicate

NeetCode: Contains Duplicate · LeetCode: 217. Contains Duplicate · Difficulty: Easy

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

Example

Text

Input:  nums = [1, 2, 3, 1]    Output: true
Input:  nums = [1, 2, 3, 4]    Output: false

Brute force: compare every pair

Compare each element with every element after it. If two are equal, there is a duplicate.

Java

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsDuplicate(new int[]{1, 2, 3, 1}));
        System.out.println(s.containsDuplicate(new int[]{1, 2, 3, 4}));
        System.out.println(s.containsDuplicate(new int[]{}));
    }
}

Output

true
false
false

Time: O(n²). Space: O(1).

Optimal: HashSet

Walk the array once and record every value seen. The set stores boxed Integer objects; add compares them with equals, so equal values are detected correctly. HashSet.add returns false when the value was already present, which signals a duplicate, so the check and the insert happen in one call.

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) {
            if (!seen.add(x)) {
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsDuplicate(new int[]{1, 2, 3, 1}));
        System.out.println(s.containsDuplicate(new int[]{1, 2, 3, 4}));
        System.out.println(s.containsDuplicate(new int[]{}));
    }
}

Output

true
false
false

Time: O(n) expected. Space: O(n).

Alternatively, sort the array with Arrays.sort(nums) (O(n log n) time, no second collection, but it reorders the caller's array) and compare neighbours: nums[i] == nums[i - 1] for any i from 1.