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

To rephrase the problem, we need to find if there are any duplicate elements in the given array. A HashSet is an appropriate data structure to solve this problem as it allows us to check if an element is already present in the set in constant time.

We can iterate over the array and check if the current element is already present in the HashSet. If it is, we can return true, else add the element to the HashSet.

If we reach the end of the array without finding any duplicate element, we can return false.

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;
}

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.