Table of contents
Question
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
Input: nums = [1,2,3,1]
Output: true
Input: nums = [1,2,3,4]
Output: false
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints
1 <= nums.length <= 10<sup>5</sup>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
Solution #1
To check whether every element is distinct (exists once) in an array, we must have a way to store and look up past values as we loop through the array.
The data structure to store these values is an object:
const lookup = {};
When we do a lookup in the object, if the value doesn't exist, we'll simply add a key-value pair to the object. The key will be the element and the value will be true:
// Element is 1
lookup[1] = true;
It's important we set the value to a boolean so that we can validate easily with a simple if statement. If the value already exists in the object, then there's no need to check the rest of the numbers. We can exit early as we know that there's already a duplicate in the array:
// Element is 1
if (lookup[1]) {
// Exit early
return true;
}
// Otherwise, add it to the object
lookup[1] = true;
Putting this all together with a for loop and the provided code:
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
const lookup = {};
for (let i = 0; i < nums.length; i++) {
// This is our element in the array
const value = nums[i];
if (lookup[value]) {
return true;
}
lookup[value] = true;
}
return false;
};
Solution #2
Another data structure we can use is a set. Sets are used to store unique values, as each value can only appear once.
By adding all the elements in the array to the set, we can skip the for loop part from Solution #1. Luckily, a set accepts an array as an argument:
// Array is nums
const set = new Set(nums);
Once we have our set created, we know all the values are unique. If there were duplicates, then they would've been removed.
In other words, the size of our set should be equal to the number of elements in the original array if there were no duplicates.
If the size of our set is smaller in comparison to the number of elements, then we know there were duplicates. A simple validation can be done:
// Set is set
// Array is nums
const containsDuplicates = set.size !== nums.length;
Putting this all together with the provided code:
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
const set = new Set(nums);
const containsDuplicates = set.size !== nums.length;
return containsDuplicates;
};
Big 0 Notation
Time complexity: o(n)
Space complexity: o(n)