# Contains Duplicate
# Links
Get the code & notes on
# Problem Description
Given an integer array nums, return true if any value appears at least twice, and return false if every element is distinct.
# Examples
Ex 1) Input: nums = [1, 2, 3, 1]
Ex 2) Input: nums = [1, 2, 3, 4]
Ex 3) Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Ex 4) Input: nums = []
# Constraints
# Thought Process
By looking at the examples, the 1st thought that comes to mind may be to simply take each value in nums, and compare it with every other value.
Basically, we'll be comparing each pair of values in nums to see if a duplicate has occurred.
To do this we'll start at the first value in nums, and compare it with each value to the right until we reach the end of nums.
Then we'll take the second value in nums, and compare it with each value to the right until we reach the end of nums.
We repeat this process until we reach the end of nums in the worst case or until we find a duplicate value.
Here's a visualization for nums = [1, 2, 3] which represents a worst case scenario:
Let's take our 1st value in nums, and compare it with each value to the right of it:
- 1st Comparison:
- 2nd Comparison:
Now, let's take our 2nd value in nums, and compare it with each value to the right of it:
- 3rd Comparison:
- The 3rd value in nums is also the last value, so there's no more comparisons to be made.
To achieve this we'll need to loop over each value in nums, and for each iteration of this loop we need to compare our current value which will denote as nums[i] with each value to the right of it.
The process of comparing nums[i] with each value to the right of it means we'll need a nested for loop that loops from nums[i + 1] to the last value in nums.
A nested for loop
Before checking for duplicate values, we can realize that if we sort nums any duplicate values will be consecutive.
Let's visualize this with an example for nums = [1, 2, 3, 1]:
Sorting nums gives us:
Now, we can loop over nums and check for duplicates values.
Looping over nums has a time complexity of O(n), and the sorting algorithm can have a time complexity as good as O(nlogn) if something like heapsort is used.
So, the overall time complexity is O(nlogn) since it's the dominating factor.
Solving this problem requires the ability to efficiently search for values, and a great way to do that is to use a hash table.
A hash table is an object that maps keys to values.
The search and insert opertions in a hash table have a time complexity of O(1).
Using a hash table will allow us to store each value in nums as a key, and we can map a value of let's say true to it if it's the first time we've seen the value.
Now, to create our hash table we can loop over nums then check to see if the key is present.
If the key is present, then we have found a duplicate, and we'll return true.
If the key isn't present, then we'll store the current value of nums as a key in our hash table with a value of true.
If no key appears twice, then nums has no duplicates, and we'll return false.
Here's a visualization of creating our hash table which we'll denote as obj for nums = [1, 2, 1]:
- 1st Iteration:
So, we'll store the value of nums[0] as a key in our hash table with a value of true.
2nd Iteration:
So, we'll store the value of nums[1] as a key in our hash table with a value of true.
3rd Iteration:
- Since the same key appeared in our hash table, a duplicate has been found in nums, so we'll return false.
# Implementation
var containsDuplicate = function(nums) {
const obj = {};
for (let i = 0; i < nums.length; i++) {
if (obj[nums[i]]) {
return true;
}
obj[nums[i]] = true;
}
return false;
};
nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));