Contains Duplicate – LeetCode problem: We need to check if the given array contains duplicates and return True if duplicates are present and False otherwise.
Link: Contains Duplicate LeetCode
Difficulty: Easy
Examples:
Input: nums = [1,2,3,2]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Solution in JavaScript
Here we use an object as a hash table(a collection of key value pairs) to store the array values, in-case we try to add an entry that already exists its a duplicate and we exit the loop.
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function (nums) {
const hashTable = {}
for (let number of nums) {
if (hashTable.hasOwnProperty(number)) {
return true
}
hashTable[number] = number
}
return false
};
Solution using Sets
This method is more or less the same. Here, we use the inbuilt Set object, which only stores unique values. Hence, when we pass the whole array, duplicates are automatically removed, resulting in a difference in length.
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function (nums) {
return new Set(nums).size !== nums.length;
};
Time Complexity: O(n)
Space Complexity: O(n)
In order to check for duplicates in the worst case, we need to complete one full iteration and store all elements in the table hence both time and space complexities are linear i.e. O(n).