Problem

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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    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;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        n = len(nums)
        for i in range(n - 1):
            for j in range(i + 1, n):
                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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public class Solution {
    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;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def contains_duplicate(self, nums: List[int]) -> bool:
        nums.sort()
        n = len(nums)
        for i in range(1, n):
            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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def contains_duplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                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, streams can be used to count the distinct elements in an array. If this distinct count differs from the length of the array, it indicates the presence of duplicates.

Code

1
2
3
4
5
6
7
8

// 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.