# # Contains Duplicate

Posted: Aug 6, 2021 Updated: Aug 6, 2022

Contains Duplicate

Get the code & notes on

Ask Questions & Share Solutions in

## # 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] Output: true since 1 appears twice.

Ex 2) Input: nums = [1, 2, 3, 4] Output: false since no value appears twice.

Ex 3) Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2] Output: true since 1, 3, and 2 appear more than once.

Ex 4) Input: nums = [] Output: false since there are no values.

## # 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 a time complexity of which is not efficient and will result in a Time Limit Exceeded error on LeetCode.

• 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));