Contains Duplicate Solutions In JavaScript
--
The contains duplicate problem provides us with an array of elements. We then have to determine if there are any duplicate elements in the array. In this article we will cover three different approaches with varying Big O time complexities.
Naive/Brute Force
First off there is the naive or brute force approach. Conceptually, we iterate through the array and compare each element to every other element in the array. This can done using a nested for loop. The outer for loop starts at the first element in the array and iterates to the second-to-last element. The inner loop starts at the element directly after the current index of the outer loop and iterates to the last element of the array. For each iteration of the inner loop we are checking to see if the element is the equal to current element of the outer loop. If we find a match we return true. If at the end of the nested for loop we don’t find a match we return false.
Here is an example of the code.
As far as time complexity this solution most certainly isn’t the most efficient. It runs in O(n²) time. With regards to space complexity, this is constant or O(1) because we are not using any extra space.
Sorting
A way that we can dramatically increase our time complexity is to take the original array, sort it, and compare the adjacent elements. If we use JavaScript’s built in sort method this would bring the time complexity down to O(n log n). The space complexity however would be increased to O(log n) also as a result of using the sort method.
After sorting we can then use a for loop to iterate through the sorted array to check if the adjacent elements are equal.
Here is an example of the code.
Using An Object
With regards to time complexity, we can make this even faster at the expense of taking up more space. This can be done by using an object which provides us the constant time lookup. First we create an empty object. We then iterate through the array and for each element we check to see if it is already included in the object. If so, we have found our match and can return true. If not, we add that element to the object and continue through the array. If at the end of the iteration we don’t find a match, we return false.
This brings the time complexity down to O(n) because we are only iterating through each element in the array once. The space complexity is increased to O(n) because in a worst case scenario we are adding each element of the array into the object.
Here is an example of the code.
These three examples show how to increase your speed by increasing your space usage. If using minimum space is a top priority then one of the slower methods might be more appropriate.
