LeetCode 217: Contains Duplicate – JavaScript Solutions

📌 Introduction

In this post, we’ll break down LeetCode 217: Contains Duplicate. We will explore three common approaches: the brute-force method, an improved solution using sorting, and the optimal HashSet approach. We'll analyze the time and space complexities for each, with all code examples in JavaScript.

👉 Original problem link: LeetCode – 217. Contains Duplicate

---

1. Problem Overview

The task is to check an array of integers, nums, and determine if any value within it appears more than once. If a duplicate is found, the function should return true. If every element is distinct, it should return false.

---

2. Examples

Example 1:

Input: nums = [1,2,3,1] Output: true Explanation: The value 1 appears at the beginning and the end of the array.

Example 2:

Input: nums = [1,2,3,4] Output: false Explanation: Each element in the array is unique.

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Explanation: Several numbers, including 1, 3, 4, and 2, appear multiple times.

---

3. Approaches

🔹 Approach #1: Brute Force (Nested Loops)

• Idea: The most straightforward solution is to compare every element with every other element in the array. We can use a nested loop where the outer loop picks an element, and the inner loop checks if that element appears again in the rest of the array.

Code (JavaScript):

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const n = nums.length

    for(let i = 0; i < n; i++){
        for(let j = i+1; j < n; j++){
            if(nums[i] === nums[j]) return true        
        }
    }

    return false
};

• Time Complexity: O(N2) - Due to the nested loops, for each element, we iterate through the rest of the array.

• Space Complexity: O(1) - No extra space is used that scales with the input size.

---

🔹 Approach #2: Sort and Scan

• Idea: A more efficient approach is to first sort the array. If any duplicates exist, they will become adjacent to each other after sorting. Then, we can simply iterate through the sorted array one time and check if any element is identical to its neighbor.

Code (JavaScript):

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const n = nums.length
    nums = nums.sort((a, b)=> a - b)

    for(let i = 0; i < n - 1; i++){
        if(nums[i] === nums[i+1]) return true
    }

    return false
};

• Time Complexity: O(NlogN) - This is dominated by the sorting algorithm.

• Space Complexity: O(1) - Sorting is done in-place, so we don't use significant extra space.

---

🔹 Approach #3: Optimal (HashSet)

• Idea: The fastest approach involves using a data structure with constant-time lookups, like a HashSet (or Set in JavaScript). We iterate through the array once. For each element, we check if it already exists in the set. If it does, we've found a duplicate and return true. Otherwise, we add the element to the set and proceed to the next one.

Code (JavaScript):

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    const set = new Set();
    for(const num of nums){
        if(set.has(num)){
            return true;
        }
        set.add(num);
    }
    return false;
};

• Time Complexity: O(N) - We iterate through the array only once, and set operations (add, has) are on average O(1).

• Space Complexity: O(N) - In the worst case (no duplicates), we will store all N elements in the set.

---

5. Key Takeaways

• ✨ This problem is a great example of the classic time vs. space tradeoff.

• ✨ The brute-force O(N^2) solution is simple but inefficient for large datasets.

• ✨ Sorting first improves the time complexity to O(N*logN) and is a good option if modifying the input array is acceptable and you want to conserve space.

• ✨ Using a HashSet offers the best time complexity (O(N)) by leveraging extra space for fast lookups.