Description

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 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Using Sorting and two pointers

One approach to solve this problem is to first sort the nums array and then use two pointers to check if the number is same as next number.

 1class Solution {
 2    public boolean containsDuplicate(int[] nums) {
 3        if (nums == null || nums.length == 0) return false;
 4        Arrays.sort(nums);
 5        for (int i = 0; i < nums.length - 1; i++) {
 6            if (nums[i] == nums[i + 1])
 7                return true;
 8        }
 9        return false;
10    }
11}
  • Time Complexity: O(n log n) because of sorting operation on nums array
  • Space Complexity: O(1)

Using Hash Data structure

The problem requires us to track if the number occurs more than once. We can use HashMap or HashSet to keep track of which numbers we have seen so far. While iterating through nums array, we check these hash data structure to check if this number was already seen. If yes, return false else at the end of iteration, we return false.

 1class Solution {
 2    public boolean containsDuplicate(int[] nums) {
 3        if (nums == null || nums.length == 0) return false;
 4        Set<Integer> set = new HashSet<>();
 5        for (int num: nums) {
 6            if (set.contains(num)) return true;
 7            set.add(num);
 8        }
 9        return false;
10    }
11}
  • Time Complexity: O(n). The lookup operation is O(1) from this set.
  • Space Complexity: O(n) because in worst case all elements may be unique and we may end up saving n numbers in set.