Coding Interview Prep: ‘Contains Duplicate’ Question with 4 Solutions and Complexity

Solution 1: Brute Force (not optimal)

/*
Brute Force method using nested for loops
Time: O(n^2)
Space: O(1)
Runtime: 50 ms
*/
var containsDuplicate_nestedForLoops = function(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;
            }
        }
    }
    return false;
}

Although it has a space complexity of O(1), this solution is not optimal because it has a time complexity of O(n²) with the nested for loops.

Solution 2: Compare array length vs set size

/*
Compare array length vs set size
Time Complexity: O(n) from creating set from array
Space Complexity: O(n) from creating a set
*/
var containsDuplicate = function(nums){
    return nums.length !== new Set(nums).size;
}

This solution is the shortest solution. However, it has both O(n) for time and space complexity. Creating a set from the array will remove any duplicate elements. So if the set size is different from the array length, there are duplicates.

Solution 3: Hashing Method

/*
Hashing method
Time Complexity: O(n)…