Remove duplication from the Javascript array with O(n) time.
Most of the interview questions ever I heard from friends and colleagues, about how to remove duplication from the array. in this article, we will focus on how effectively we can remove duplication and return a unique array. let’s jump to the problem and their solution.
Problem
let say we have an array with duplication [1,2,2,3,3] and we want to get a unique array [1,2,3].
Solution # 1 using nested loop
if you look at the “getUniqueArray” function take an array. it consists of a nested loop. outer loop iterate over the “input array” and nest loop check for uniqueness.so the time complexity of this algorithm is Big O squared O(n²).
hmm Big O squared O(n²) expansive. Can we make it to O(n) time 🤔?
Let try to make it to 😍(n) time.
Solution # 2 using javascript object as Hashes.
The time complexity of accessing javascript object property is O(1) time. let use this in our existing algorithm.
Instead of the loop over to find duplication we use a javascript object which behaves like a hash.
The tradeoff here is the space complexity and time complexity. In the first algorithm, we have time complexity and in the second algorithm we have space complexity by adding “tempObject”.
Solution # 3 using Set
This is another cool thing in Javascript ES6 which can be used to make array unique.
Comparing the above Three approaches using javascript Tool console.time and creating 10000 items in an array.
solution #1
102.072ms
Solution #2 (object as a hash)
6.361ms
Solution #3(set)
4.525ms
Note: the above value will differ from system to system even if run the function twice because of v8 use memoization.
what happens if we have an array of objects.
as we know that solution 3 (win) but what happens if we have an array of objects. we can not use Set but we can use the second solution.
if you look at the example “space complexity” is increasing by putting data in two places like “tempObject” object and unique array. we can reduce space complexity by using the following code.
so here we reduce the space complexity by just create an object and then retrieving the value from the object as an array but algorithm time complexity will O(n)+O(n) forEach + values().
How to keep duplicates of an Array.
someone ask on stack overflow.
here is my Answer. I use the same object hashing technique.
