For a list of all coding patterns questions and tests, checkout my GitHub repo

Problem: Contains Duplicate

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.

Example:
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The element 1 occurs at indices 0 and 3.

Example:
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: No duplicate values are found.

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

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

There are multiple ways of solving this problem. From the most naive solution, which is to run nested loops and compare if the same elements exists elsewhere to a less naive solution where you can sort the elements in the array and compare successive elements. If you see equal elements, you can return true. The nested loops method takes O(n^2) time whereas the sorting method takes O(nlong n) time. However, the space complexity id O(1) in both cases since we are using the same array to check for duplicates.

Another approach which is of O(n) time complexity and O(n) space complexity is to use a hashset to track each element and to detect duplicates. Using Hashmaps and Hashsets is usually the best approach to detect duplicates.

The way this approach works is that we create a hashset. For each element in the array, we check if it already exists in the hashset. If it does, we return true because we found a duplicate. If we don't find it, we add the element to the hashset and move on to the next one, where we do the same thing again.

Time complexity: O(n)
Space complexity: O(n)

public boolean containsDuplicate(int[] nums) {
    Set numSet = new HashSet<>();

    for(int n: nums) {
        if(numSet.contains(n)) {
            return true;
        }

        numSet.add(n);
    }

    return false;
}