Problem

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.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Solution

Method 1 - Brute Force

Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop. This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.

Code

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

Complexity

  • Time Complexity: O(n^2)
  • Auxiliary Space: O(1)

Method 2 - Sorting the Array and Compare Adjacent Array

Code

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

Complexity

Sorting takes O(n log n) time, but as they are integers we can use counting sort, which takes O(n) time.

  • Time complexity = O(n log n) OR O(n)
  • Space Complexity = O(1)

Method 3 - Using Hashset

Code

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

Complexity

  • Time complexity = O(n) for looping on array and checking in set takes O(1) time.
  • Space Complexity = O(n) for storing values in set.

Method 4 - Using Count

In Java 8, we can make use of streams to count distinct elements present in the array. If the distinct count is not same as the length of the array, array contains a duplicate.

Code

Java
// Generic function to check for duplicates in an array
private static <T> boolean checkForDuplicates(T... array)
{
 Long distinctCount = Stream.of(array)
 .distinct().count();

 return array.length != distinctCount;
}

Complexity

  • O(n) - In java distinct() removes duplicate from stream, using hashset internally.