Removing Duplicate Items in JavaScript ES6

I think everyone, just like me, has had to remove duplicate items from an Array list at some point. But is the way we learned actually the best one?

In this article I’ll show you my point of view, the way I found to remove duplicate items from a list with over 1,000,000 items in my day to day at @squidit, whether the array holds primitive types or not.

The common way#

I believe the most common way we know is looping through an Array and checking, on every iteration, whether that item is already in the new array or not.

1
/**
2
 * @desc Generates an array of size N with random numbers, respecting N
3
 * @param {number} length
4
 */
5
function generateRandomArray(length) {
6
  return Array.from(Array(length), () => parseInt(Math.random() * length));
7
}
8

9
const randomList = generateRandomArray(1000) // An array with 1000 random numbers
10
const uniqueList = [] // List for the unique array
11

12
for(const value of randomList) {
13
  //  If the value isn't in uniqueList, add it
14
  if (!uniqueList.includes(value)) uniqueList.push(value)
15
}
16
console.log(`uniqueList has ${uniqueList.length} itens`)

Which produces the following output:

This might even work fine for a small list of a few thousand items.

If we use console.time and console.timeEnd to check how long this operation takes, we’ll see it’s super fast.

1
//  Rest of the code
2

3
console.time('Remove duplicated items') // We add
4
for(const value of randomList) {
5
  //  Check from the previous code...
6
}
7
console.timeEnd('Remove duplicated items')

Produces the following output:

What would happen if we happened to increase this dataset, say to a list with 100,000 items?

1
//  Rest of the code ...
2

3
// equals 10^5, which is the same as 100,000
4
const randomList = generateRandomArray(10 ** 5)
5
const uniqueList = [] // List that will hold the unique items
6

7
console.time('Remove duplicated items')
8
for(const value of randomList) {
9
  //  If the value isn't in uniqueList, add it
10
  if (!uniqueList.includes(value)) uniqueList.push(value)
11
}
12
console.timeEnd('Remove duplicated items')

Produces the following output:

Print-time-to-remove-duplicated-items-with-100k

And if we increase it to 200,000, for example, the time already increases drastically.

Print-time-to-remove-duplicated-items-with-200k

The problem#

Using for or .reduce the premise would still be the same:

Loop through the array.
Check whether the value exists in the new array.
Add it to the array.

For every iteration, you need to do a second iteration over uniqueArray to check whether the value is already in there. In programming, this is called O(n)², where n dictates the number of operations your application will run. So the number of operations for this algorithm grows exponentially as the number of items grows.

Let’s look at an example with the following code:

1
// Rest of the code
2

3
// Loops 10 times, 10k at a time, up to 100k
4
for (let length = 1; length <= 100000; length += 10000) {
5
  // For each iteration, generates a new array.
6
  const randomList = generateRandomArray(length)
7
  const uniqueList = [] // List that will hold the unique items
8

9
  console.log(`List size of ${randomList.length}`)
10
  console.time(`Remove ${randomList.length} duplicated items`)
11
  for (const value of randomList) {
12
    // If the value isn't in uniqueList, add it
13
    if (!uniqueList.includes(value)) uniqueList.push(value)
14
  }
15
  console.timeEnd(`Remove ${randomList.length} duplicated items`)
16
  console.log('---------')
17
}

You can see the time growing exponentially when we print how long the operation takes to finish based on the number of items.

Print-exponential-duration-to-remove-duplicated-items

Using Set#

In JavaScript we have an object called Set. It guarantees values are stored only once, meaning whenever we try to add a value that’s already in the structure, that value won’t be added.

1
const set = new Set();
2

3
set.add(1) // [1]
4
set.add(2) // [1,2]
5
set.add(3) // [1,2,3]
6
set.add(2) // [1,2,3]
7

8
console.log(set) // Set(3) { 1, 2, 3 }

Set accepts objects too, but it won’t remove duplicates among them because objects, as we know, are passed by reference in JavaScript:

1
const set = new Set();
2

3
set.add({ a: 1, b: 2 }) // Object gets added [{}]
4
set.add({ a: 10, b: 20}) //  [{},{}]
5

6
// Even though the values are the same,
7
// the object is still different,
8
// because it's referenced
9
// at a different memory address
10
set.add({a: 1, b: 2}) //  [{}, {}, {}]
11

12
console.log(set) // Set(3) { { a: 1, b: 2 }, { a: 10, b: 20 }, { a: 1, b: 2 } }

Using Set to remove duplicates#

When we use the Set API to remove duplicate items from an array, we notice the time difference between using Set and using a for loop.

1
/**
2
 * @desc Generates an array of size N with random numbers, respecting N
3
 * @param {number} length
4
 */
5
function generateRandomArray(length) {
6
  return Array.from(Array(length), () => parseInt(Math.random() * length));
7
}
8

9
// Loops 10 times, 10k at a time, up to 100k
10
for (let length = 1; length <= 100000; length += 10000) {
11
  // For each iteration, generates a new array.
12
  const randomList = generateRandomArray(length)
13

14
  console.log(`List size of ${randomList.length}`)
15
  console.time(`Remove ${randomList.length} duplicated items using Set API`)
16
  const uniqList = Array.from(new Set(randomList))
17
  console.timeEnd(`Remove ${randomList.length} duplicated items using Set API`)
18
  console.log('---------')
19
}

Produces the following output:

Print de tempo para remover itens duplicados usando Set

This happens because, unlike the loop, we still need to iterate over the array n times, but on each iteration the Set API guarantees we’re adding a single unique value. And since the Set object implements the iterable interface, we can turn it into an Array.

1
Array.from(new Set([1,2,3,4,1,2,3,4])) // Produces [1,2,3,4]

Duplicates in a list of objects#

In the real world we know lists aren’t made up of primitive types only. So how would we handle objects?

Instead of using Set, we use Map together with the Array API’s .reduce method. But for that I need to give you an overview of what Map is.

Maps#

The Map structure works as a key-value data structure, or a HashTable, which, in short, is a list of key-value data where every item added has a related id, or key. That makes it possible to do a fast lookup using just the key, without needing to loop through the whole list to find the item.

1
const map = new Map()
2

3
map.set(1, { a: 1, b: 2, b: 3 }) // Map(1) { 1 => { a: 1, b: 3 } }
4
console.log(map)
5

6
map.set(2, { a: 10, b: 20, c: 30 }) //  Map(2) { 1 => { a: 1, b: 3 }, 2 => { a: 10, b: 20, c: 30 } }
7
console.log(map)
8

9
// Overwrites the object at key 1.
10
map.set(1, { a: 100 }) // Map(2) { 1 => { a: 100 }, 2 => { a: 10, b: 20, c: 30 } }
11

12
map.get(1)  // { a: 100 }
13
map.get(2)  // { a: 10, b: 20, c: 30 }
14
map.get(3)  // undefined, because there's nothing at key 3

And of course, the key doesn’t have to be a numeric value. It can be any type of data:

1
const map = new Map()
2

3
map.set('samsung', ['S10', 'S20']) // Map(1) { 'samsung' => [ 'S10', 'S20' ] }
4

5
map.set('outro valor', [2, 3, 4, 5]) // Map(2) { 'samsung' => [ 'S10', 'S20' ], 'outro valor' => [ 2, 3, 4, 5 ] }

Using Map to remove duplicate items#

Now that we have an idea of how to use Map, we can take advantage of .reduce to generate a unique array from a list with duplicates.

First, let’s create a function that generates a list with the same object, varying only the id of each item.

1
/**
2
 * @desc Generates a list with the same object,
3
 * where the id will be random
4
 * @param {number} length
5
 */
6
function generateRandomObjectList(length) {
7
  const defaultObject = {
8
    name: 'Guilherme',
9
    developer: true
10
  }
11
  return Array.from(Array(length), () => {
12
    const randomId = parseInt(Math.random() * length)
13
    return {
14
      ...defaultObject,
15
      id: randomId
16
    }
17
  });
18
}

Now let’s create a Map object from the generated array,
where the Map’s id will be the user’s id. That way we remove duplicate IDs from the list:

1
const listObjectWithRandomId = generateRandomObjectList(10 ** 5) // 100k
2
const objectMap = listObjectWithRandomId.reduce((map, object) => {
3
  map.set(object.id, object);
4
  return map
5
}, new Map())

Since Map is also an iterable object, we just need to use the Array.from function:

1
const uniqList = Array.from(objectMap, ([_, value]) => value)

The whole code would look like this:

1
/**
2
 * @desc Generates a list with the same object,
3
 * where the id will be random
4
 * @param {number} length
5
 */
6
function generateRandomObjectList(length) {
7
  const defaultObject = {
8
    name: 'Guilherme',
9
    developer: true
10
  }
11
  return Array.from(Array(length), () => {
12
    const randomId = parseInt(Math.random() * length)
13
    return {
14
      ...defaultObject,
15
      id: randomId
16
    }
17
  });
18
}
19

20
const listObjectWithRandomId = generateRandomObjectList(10 ** 5) // 100k
21

22
console.time('uniq List usando Map') // To measure how long the operation takes
23
const objectMap = listObjectWithRandomId.reduce((map, object) => {
24
  map.set(object.id, object);
25
  return map
26
}, new Map())
27

28
const uniqList = Array.from(objectMap, ([_, value]) => value)
29
console.timeEnd('uniq List usando Map')
30
console.log(`Lista duplicada: ${listObjectWithRandomId.length}`)
31
console.log(`Lista duplicada: ${uniqList.length}`)

Print of time to remove duplicated items using Map

Conclusion#

Even though libraries like lodash have functions to remove duplicate items, importing an entire library to solve a problem you can solve with a few lines of native code ends up being unnecessary.