JavaScript: remove duplicates from a list of objects

This is probably one of the most basic things that you can do. I saw a lot of answers to this question which are either wrong or two slow (think Big-O square complexity runtime). The most elegant solution I found, for future reference first sorts the collection and then uses reduce in order to remove duplicates.

Let’s take an example collection of objects:

As we see we have a collection of countries where each object is composed of an id and a string, the country name.

Now let’s say that we wish to remove all countries with duplicate names. One obvious way is to take each element and then visit all other elements looking for duplicates. It can be done in-place or with the help of an auxiliary collection. However, this algorithm is of square runtime complexity.

Here’s a better way:

What we’re doing here is that, first of all, we sort the collection by the property we’re interested in removing duplicates. This clusters objects by their equal property. Next we apply reduce and, at each, go we check if the last element in the accumulator has the same name as the current one. If it does, we just drop the current one, otherwise we add it to the accumulator.

Runtime complexity of this is O(n log n) because the dominant here is the sorting. Reducing only takes linear complexity. Memory-wise this has constant complexity because we only need additional space for the accumulator.

Leave a Reply

Your email address will not be published. Required fields are marked *