217. Contains Duplicate

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

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 217. Contains Duplicate

Problem statement

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.

Approach

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
}

Code

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;
};

Complexity

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).