# Contains Duplicate

By: J the Code Monkey
Posted: Aug 6, 2021 Updated: Jul 3, 2024

Contains Duplicate

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

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

Made by & for Code Monkeys 🐵