How to Solve the Contains Duplicate Problem in JavaScript

The Contains Duplicate problem is a common algorithmic challenge where the goal is to determine if an array of numbers contains any duplicate elements. This problem can be solved using a variety of approaches, each with different time and space complexities.

In this post, we will explore multiple ways to solve this problem in JavaScript, starting with a brute-force solution, followed by a more efficient sorting-based solution, and ending with the most optimized solution using a Set.

Problem Definition

You are given an array of integers nums. The task is to determine if any value appears at least twice in the array. The function should return true if any value appears more than once, otherwise it should return false.

Example:

Input: nums = [1, 2, 3, 1]
Output: true

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

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

Constraints:

• The array size can range from 1 to (10^5).
• Each element can be as large as (10^9) or as small as (-10^9).

Let's explore different solutions to this problem in JavaScript.

Solution 1: Brute-Force Approach

Approach:

The brute-force method involves comparing every element with every other element in the array. If two elements are found to be the same, the function returns true. If no duplicates are found by the end of all comparisons, the function returns false.

Code Implementation:

function containsDuplicate(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true;  // Duplicate found
            }
        }
    }
    return false;  // No duplicates
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n²) because of the two nested loops.
• Space Complexity: O(1) since no extra space is used beyond a few variables.

Explanation:

This brute-force solution uses two loops: the outer loop picks an element, and the inner loop compares it with all the elements that come after it. If any pair of elements are equal, the function returns true. If no duplicates are found by the end of the loops, the function returns false.

Drawbacks:

This approach is inefficient for large arrays since its time complexity is O(n²). As the array size increases, the time taken to complete the function grows significantly, making it impractical for large datasets.

Solution 2: Sorting Approach

Approach:

A more efficient way to solve this problem is by first sorting the array. After sorting, any duplicates will appear next to each other. We can then simply check if any two consecutive elements are the same.

Code Implementation:

function containsDuplicate(nums) {
    nums.sort((a, b) => a - b);  // Sort the array
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) {  // Compare adjacent elements
            return true;
        }
    }
    return false;
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n log n) because sorting dominates the time complexity.
• Space Complexity: O(1) if sorting is done in place (JavaScript's sort() sorts the array in place).

Explanation:

In this solution, we first sort the array using the sort() method, which rearranges the elements in ascending order. After sorting, we loop through the array and check if any two consecutive elements are equal. If they are, we return true. If the loop completes without finding duplicates, the function returns false.

Benefits and Drawbacks:

• Benefits: This approach is faster than the brute-force method because sorting reduces the number of comparisons.
• Drawbacks: Sorting modifies the original array, which might not be desirable in some cases. Additionally, the time complexity of sorting is O(n log n), which is still not optimal for very large datasets.

Solution 3: Using a Set (Optimal Solution)

Approach:

The most efficient way to solve this problem is by using a Set. A Set is a collection of unique values. As we iterate through the array, we can check if the current element is already in the set. If it is, we return true because a duplicate has been found. If not, we add the element to the set and continue.

Code Implementation:

function containsDuplicate(nums) {
    const seen = new Set();  // Create an empty set
    for (const num of nums) {
        if (seen.has(num)) {  // Check if num is already in the set
            return true;
        }
        seen.add(num);  // Add num to the set
    }
    return false;
}

// Test the function
const nums = [1, 2, 3, 1];
console.log(containsDuplicate(nums));  // Output: true

Time and Space Complexity:

• Time Complexity: O(n) since we are iterating through the array once, and set lookups and insertions are O(1) on average.
• Space Complexity: O(n) because we need space for the set to store the elements.

Explanation:

This solution leverages the power of JavaScript's Set to efficiently store unique elements. As we loop through the array, we check if the current element is already in the set. If it is, we immediately return true, indicating that a duplicate was found. Otherwise, we add the element to the set and continue. If no duplicates are found after the loop completes, the function returns false.

Benefits and Drawbacks:

• Benefits: This solution has linear time complexity, making it the most efficient option. Set operations (insertion and lookup) are very fast, with an average time complexity of O(1).
• Drawbacks: The main drawback is the extra space needed for the set, which is O(n), but this is usually a reasonable trade-off for the efficiency gained.

Edge Cases

When solving the Contains Duplicate problem in JavaScript, it’s important to account for various edge cases to ensure that the solution works in all scenarios. Below are some key edge cases that should be considered when implementing the solution:

1. Empty Array:

If the input array is empty, there are no elements to compare, so the function should return false.

Example:

const nums = [];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since there are no elements in the array, there cannot be any duplicates, so the function should return false.

2. Array with One Element:

If the array contains only one element, it’s impossible to have duplicates, so the function should return false.

Example:

const nums = [1];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since there is only one element, it cannot have duplicates, so the function should return false.

3. Array with All Unique Elements:

If the input array contains all unique elements (i.e., no duplicates), the function should return false.

Example:

const nums = [1, 2, 3, 4, 5];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since all elements are unique, the function should return false.

4. Array with All Duplicate Elements:

If the array consists entirely of the same element repeated multiple times, the function should return true.

Example:

const nums = [1, 1, 1, 1];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: Since every element in the array is the same, the function should return true.

5. Array with Negative Numbers:

The array may contain negative numbers. The solution should handle these correctly and identify duplicates among them.

Example:

const nums = [-1, -2, -3, -1];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element -1 appears twice, so the function should return true.

6. Array with Negative and Positive Numbers:

The array may contain both negative and positive numbers. The solution should correctly distinguish between these numbers.

Example:

const nums = [-1, 2, -3, 3];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since all elements are unique, the function should return false.

7. Array with Zeros:

The array may contain zero values, and the solution should correctly handle multiple zeros.

Example:

const nums = [0, 1, 2, 0];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element 0 appears twice, so the function should return true.

8. Array with Mixed Duplicates and Unique Elements:

The array may contain a mix of unique and duplicate elements. The function should return true as soon as a duplicate is found.

Example:

const nums = [1, 2, 3, 2];
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The element 2 appears twice, so the function should return true.

9. Array with Large Numbers:

The array may contain very large or very small integers within the range [-10^9, 10^9]. Ensure that the solution handles these values correctly.

Example:

const nums = [-1000000000, 1000000000];
console.log(containsDuplicate(nums));  // Output: false

• Expected Output: Since the two elements are different and within the valid range, the function should return false.

10. Array with Maximum Length (100,000 elements):

If the array contains the maximum number of elements (100,000), the solution should handle the large dataset efficiently. This is especially important for the brute-force solution, which may fail or run too slowly for such input sizes.

Example:

const nums = Array.from({ length: 100000 }, (_, i) => i);
nums[99999] = 99998;  // Add a duplicate
console.log(containsDuplicate(nums));  // Output: true

• Expected Output: The array contains a duplicate at the last position, so the function should return true. The solution should efficiently handle the large input size.

Conclusion

In this post, we explored three different solutions for solving the Contains Duplicate problem in JavaScript:

1. Brute-force approach: A simple but inefficient solution with O(n²) time complexity.
2. Sorting approach: A faster solution with O(n log n) time complexity, but it modifies the original array.
3. Set approach: The optimal solution with O(n) time complexity and O(n) space complexity, making it the best choice for large datasets.

When solving this problem in practice, the set-based solution should be your first choice due to its efficiency in both time and ease of implementation.