How to Remove Duplicates from an Array in JavaScript
A standard interview question that I have encountered multiple times in my engineering journey is the classic “remove duplicates from an array” problem. This may be asked in a phone screen, online, or during an on-site. While many tech companies may not ask this specific question, it is a great practice interview problem that can help grow our time complexity understanding and further enhance our programming proficiency.
Table of Contents
- The Remove Duplicates Problem
- Standard ways to remove duplicates
- Brute force solution - O(n2)
- Solution with hash-map - O(n)
- Removing duplicates with ES6
- Using a
Set
- Using
filter()
- Using
filter()
andindexOf()
- Using a
- Standard ways to remove duplicates
- Conclusion
- Additional Resources
TL;DR
Remove duplicates with a Set (ES6)
const unique = [...Set([1,1,2,2,5,5,3])]; //[1,2,5,3]
Remove duplicates with a hash-map (no ES6)
function removeDuplicates(array) {
const result = [];
const map = {};
for (let i = 0; i < array.length; i++) {
if (map[array[i]]) {
continue;
} else {
result.push(array[i]);
map[array[i]] = true;
}
}
return result;
}
Now that you see where we are heading, how did we get there? Let’s start with the problem statement and push forward!
The Removing Duplicates Problem
From the book Programming Interviews Exposed:
Given an unsorted list of integers, write a function that returns a new list with all duplicate values removed.
So how might we approach this problem?
Brute force
One solution is to have two arrays. One for our input and one for our output. The basic algorithm consists of looping through the original array
(i.e. list) and for every element in the array, check to see if it exists in our result
array. If the element exists in result
skip to the next element, if not, add it to the result
array. Once complete, return result
.
function removeDuplicates(array) {
const result = [];
for (let i = 0; i < array.length; i++) {
let exists = false;
for (j = 0; j < result.length; j++) {
if (array[i] === result[j]) {
exists = true;
break;
}
}
if (!exists) {
result.push(array[i]);
}
}
return result;
}
Running the code is straightforward.
const duplicates = [5,2,3,2,5,5,1,7,2,1,5,8];
removeDuplicates(duplicates); //[ 5, 2, 3, 1, 7, 8 ]
This is a brute force solution with a O(n2) time complexity. This algorithm’s time complexity stems from the fact that we are looping through two arrays. Can we get to this to linear time, i.e. O(n)? Yes we can, by using a hash-map!
Remove duplicates using a hash-map
In our brute force solution, we loop through the array twice, what if we were to loop through just once? We can do this if we use an object to keep track of key value pairs, i.e. our “hash-map”. The “key” is the element in the array, and the “value” is either true or falsy (undefined
). This map keeps track of whether we have previously added the current element to our result
array or not.
function removeDuplicates(array) {
const result = [];
const map = {};
for (let i = 0; i < array.length; i++) {
if (map[array[i]]) {
continue;
} else {
result.push(array[i]);
map[array[i]] = true;
}
}
return result;
}
Again we can run this code to see the results.
const a = [1,1,2,3,3,4,4,5,5];
const b = [2,3,3,1,2,7,5,5,4,9,4,14];
const c = [5,2,3,2,5,5,1,7,2,1,5,8];
removeDuplicates(a) //[1,2,3,4,5]
removeDuplicates(b) //[2,3,1,7,5,4,9,14]
removeDuplicates(c) //[5,2,3,1,7,8]
The general idea of this solution is to maintain a mapping of our elements to a boolean value of whether the element has been added to our result
array or not. Stated differently, the boolean represents either yes we have added this element to the result
(true
) or no we have not (false
).
The chart below illustrates the state of the variables, in the simple case of an array [1,1,2]
.
i |
array[i] |
map[array[i]] |
result |
0 | 1 | undefined | [1] |
1 | 1 | true | [1] |
2 | 2 | undefined | [1,2] |
What about using ES6?
OK, Ajahne, this is cool and all, but can we leverage ES6?
Definitely, please note, that some interviewers may veto built-in methods or utilizing certain objects.
Oh, really?
Yeah, they may do this to get a better sense of how you approach a problem. In that case, it is still worth mentioning that “I would use a set in this way…” or “I could leverage filter like so…”. Showing your knowledge of the language will definitely get you some brownie points!
Got it. But I’m still waiting…
Bet, let me upgrade you!
Removing duplicates using a Set
My preferred method of removing duplicates from an array is to use a Set
. By definition, a set can only contain unique values, so it is the perfect data structure to solve this problem.
const array = [1,1,2,3,3,4,4,5,5];
const set = new Set(array);
const uniqueArray = [...set];
console.log(uniqueArray);
What we do in the above code is create an array, make a new Set using our array as an initial parameter to the Set’s constructor, and then use the spread operator to transform our set into an array.
Furthermore, you can one line this solution.
const unique = [...new Set(array)];
Cool, so how else might we do this?
Remove duplicates using Array.filter()
We can upgrade our original optimized solution by replacing our for
loop, with filter
. The filter
function takes a callback and returns a new array comprised only of elements that pass our test.
function dedupUsingFilter(a) {
const map = {};
return a.filter(element => {
if (map[element]) {
return false
} else {
map[element] = true;
return true;
}
});
}
const a = [1,1,2,3,3,4,4,5,5];
const b = [2,3,3,1,2,7,5,5,4,9,4,14];
const c = [5,2,3,2,5,5,1,7,2,1,5,8];
dedupUsingFilter(a) //[1,2,3,4,5]
dedupUsingFilter(b) //[2,3,1,7,5,4,9,14]
dedupUsingFilter(c) //[5,2,3,1,7,8]
Remove duplicates using Array.filter()
and Array.indexOf()
Building on the previous example, we can leverage indexOf
in our callback to filter out elements that appear more than once.
function dedupUsingFilterAndIndexOf(a) {
return a.filter((element, index) => a.indexOf(element) === index);
}
const a = [1,1,2,3,3,4,4,5,5];
const b = [2,3,3,1,2,7,5,5,4,9,4,14];
const c = [5,2,3,2,5,5,1,7,2,1,5,8];
dedupUsingFilterAndIndexOf(a) //[1,2,3,4,5]
dedupUsingFilterAndIndexOf(b) //[2,3,1,7,5,4,9,14]
dedupUsingFilterAndIndexOf(c) //[5,2,3,1,7,8]
For each element in the array, we check to see if it’s index matches the current index. This works because indexOf
returns the first index at which a given element can be found and -1 if it does not exist. So, if we have an array with duplicate elements, the indexes of each will be different, but a call to indexOf
will return the first index. So in our check of a.indexOf(element) === index
, if these indexes are different, then this element is not the first element with this value and should not be added to our resulting array.
Let’s look at the scenario when we have an array [1,2,2]
index |
element |
indexOf(element) |
result |
note |
0 | 1 | 0 | [1] | the element’s index and the first index of this element match, so we add it to the result |
1 | 1 | 0 | [1] | when we look up 1, its first index (indexOf) is 0, so we know this is a duplicate, and skip it |
2 | 2 | 2 | [1,2] | the element’s index and the first index of this element match, so we add it to the result |
Conclusion
There are numerous ways to remove duplicates from an Array in JavaScript and we explored many key solutions within this post. It is worth learning these different techniques to widen our JavaScript skillset and leverage our Big O understanding as we build optimized solutions that will help us not only in our interviews, but on the next job and beyond!
Check out the additional resources below and happy coding!