Contains Duplicate

Question

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example:

Input: [1,2,3,1]
Output: true

Input: [1,2,3,4]
Output: false

Analyzation

Sort

This method uses a sorting algorithm. Since comparative sorting algorithms, such as heap sorting, can have O(nlogn) time complexity in the worst case. Therefore, sorting is often a good preprocessing method. After sorting, we can scan the sorted array to find if there are any consecutive duplicate elements.

The Code

class Solution {
    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;
    }
}

Time & Space Complexity

• Time Complexity: O(nlogn). The complexity of sorting is O(nlogn), and the complexity of scanning is O(n). The whole algorithm is mainly determined by the sorting process, so it is O(nlogn).
• Space Complexity: O(1). This depends on the implementation of the specific sorting algorithm. Generally speaking, using heap sorting is O(1).

Optimization

HashSet

From Method 1, we know that the time complexity of the search operation on the unordered array is O(n), and we will call the search operation repeatedly. Therefore, using a data structure with a faster search time will speed up the entire algorithm. There are many data structures commonly used as dynamic collections, such as binary search trees and hash tables. The operations we need here are search and insert. For a balanced binary search tree (TreeSet or TreeMap in Java), the time complexity of search and insert are both O(logn). For hash tables (HashSet or HashMap in Java), the average time complexity of search and insert is O(1). Therefore, by using a hash table, we can achieve linear time complexity to solve the problem.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        for(int i : nums){
            if(set.contains(i)){
                return true;
            }
            set.add(i);
        }
        
        return false;
    }
}

Time & Space Complexity

• Time complexity: O(n). search() and insert() are used n times each, and each operation takes a constant time.
• Space complexity: O(n). The space occupied by the hash table has a linear relationship with the number of elements.