Contains Duplicate

Problem Statement

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

Approach

The most straightforward approach to solve this problem is to sort the array and then check if there are any duplicate elements. If we find any duplicate elements, we can return true, else return false.

public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for(int i=1; i < nums.length; i++){
        if(nums[i] == nums[i-1]){
            return true;
        }
    }
    return false;
}

Or count the number of distinct elements in the array and compare it with the length of the array. If the number of distinct elements is less than the length of the array, then there are duplicate elements in the array.

public boolean containsDuplicate(int[] nums) {
    return Arrays.stream(nums).distinct().count() != nums.length;
}

But both of these approaches have a time complexity of $O(n \log n)$, where $n$ is the number of elements in the array.

Can we optimize the runtime by compromising on the space complexity? It turns out we can!

What we need is a data structure that allows us to check if an element is already present in the array in constant time and a HashSet is the perfect data structure for this.

A HashSet allows us to store elements in a collection and provides constant time operations for adding, removing, and checking if an element is present in the collection. On a high level, what we need to do is:

1. Create a HashSet to store the elements of the array.
2. Iterate over the array and for each element:
   • Check if the element is already present in the HashSet.
   • If it is present, return true.
   • If it is not present, add the element to the HashSet.

Implementation

Here is a java implementation of the approach:

public boolean containsDuplicate(int[] nums) {
    Set<Integer> cache = new HashSet<>();
    for(int elem : nums){
        if(cache.contains(elem)){
            return true;
        }else{
            cache.add(elem);
        }
    }       
    return false;
}

Additionally, as we know that if the element is already present in a HashSet, the add method will return false. We can use this to our advantage to simplify the code as follows:

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

Complexity Analysis

The time complexity for this approach is $O(n)$, where $n$ is the number of elements in the array. We iterate over the array once and perform constant time operations for each element.

The space complexity is also $O(n)$ - for all unique elements, due to the HashSet used to store the elements of the array.