Question: 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 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Solution (Java):
We can solve it by using HashSet. While adding array elements into HashSet, we can check if the element already exists in it. If yes, then it confirms the element already exists and its the duplicate.
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for(int n : nums){
if (set.contains(n))
return true;
set.add(n);
}
return false;
}Time Complexity: O(n)
We iterate through the input array which takes O(n) and the lookup in HashSet is O(1). The final time complexity would be O(n)
Space Complexity: O(n)
As we are using additional space with HashSet, we would have O(n), space complexity.