LeetCode Problems

In this tutorial we will solve 217. Contains Duplicate problem from leetcode.

Reference: 217. Contains Duplicate

In this problem we have an input integer array `nums`

and we have to return `true`

if any value appears **at least twice** in the array and we have to return `false`

if all the values in the array are distinct.

Example from leetcode.

```
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
```

```
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
```

In example 1, we can see that number 1 appear twice hence we will return `true`

.

In example 2, all the numbers are distinct so we return `false`

.

And in example 3, we have multiple numbers that appear more than twice hence we return `true`

.

To solve this problem we will have to keep track of the number of times we have see a given element in the `nums`

array.

For example, if our input array `nums`

is `[1, 2, 3, 1]`

then we will go through the array and for each new element we will add that element in a hash map and set the value to `true`

. If we again encounter an element that we have already saved in the has map then this will indicate that we have duplicates in the array.

This is how the steps will look like.

```
hashmap = {}
nums = [1, 2, 3, 1]
^
1 is not present in the hash map, make new entry.
hashmap = {
1: true
}
nums = [1, 2, 3, 1]
^
2 is not present in the hash map, make new entry.
hashmap = {
1: true,
2: true
}
nums = [1, 2, 3, 1]
^
3 is not present in the hash map, make new entry.
hashmap = {
1: true,
2: true,
3: true
}
nums = [1, 2, 3, 1]
^
1 is present in the hash map, we found a duplicate
hashmap = {
1: true, <---- 1 is already present in the hash map
2: true,
3: true
}
```

JavaScript

```
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
const hm = new Map();
for(let n of nums) {
if(hm.has(n)) return true;
hm.set(n, true);
}
return false;
};
```

**Time complexity: O(n)**

In the worst case, we will traverse the whole array and if there are n elements then our time complexity will be O(n).

**Space complexity: O(n)**

In the worst case, our hash map will save n elements. Thus the space complexity will be O(n).

ADVERTISEMENT