What's a better algorithm to remove duplicates from an array of objects?

Question

I have an array of objects that looks something like (rough example):

[{id:1, stuff:moreStuff}, {id:6, manyStuff,Stuffing}, {id:4, yayStuff, stuff}, {id:6, manyStuff, Stuffing}]

The problem is that in the array, there are several duplicate objects. The current solution I've thought of so far is something along the lines of this:

const DuplicateCheck = []
const FinalResult = []

for (let i = 0; i < ArrayOfObjects.length; i++) {
    let isPresent = false;
    for (let j = 0; j < duplicateCheck.length; j++) {
        if (ArrayOfObjects[i].id == duplicateCheck[j]) {
            isPresent = true;
        }
    }
    if (isPresent = false) {
        DuplicateCheck.push(ArrayOfObjects[i].id
        FinalResult.push(ArrayOfObjects[i]
    }
}

Now after learning big O, it seems like this is a very inefficient way to go about doing this problem. So my question is, is there a better, more efficient way to solve this problem?

One approach: Sort into array 2, copy back. If the array is sorted, duplicates appear one after the other so you only need to look at the previous value. O ( n log n ) sort + O ( n ) copy. There might be better approaches if you google, like adding to hash table and copying back from that? — Dave S, Jul 27 '20 at 20:32
If one were to map the objects to `JSON` strings, create a new `Set` from that, create a new `Array` from the set, then map the now unique elements back to objects, what would be the `O` of that? — GirkovArpa, Jul 27 '20 at 20:44
Does this answer your question? [Remove duplicates from an array of objects in JavaScript](https://stackoverflow.com/questions/2218999/remove-duplicates-from-an-array-of-objects-in-javascript) — Heretic Monkey, Jul 27 '20 at 20:44
I don't get points for closing questions as a dupe. You'd know that if you read the [privileges](https://stackoverflow.com/help/privileges/close-questions) page instead of going with your prejudices. Also, you're not the OP @GirkovArpa, so why are you even responding? — Heretic Monkey, Jul 27 '20 at 20:49
@GirkovArpa: Removing duplicate questions is a community service, earning no reputation points or other rewards. — Scott Sauyet, Jul 27 '20 at 20:50
Based on the aggressiveness of dupe-finders I'd never have imagined that. — GirkovArpa, Jul 27 '20 at 20:51
My last question was attacked by dupe-finders 3 times in the name of "community service." — GirkovArpa, Jul 27 '20 at 20:52
@GirkovArpa: the site as a whole is better when there are definitive answers to common questions. That's why we have duplicate-closing. Various people spend less or more amounts of effort to check for duplicates, but when they'r found it's a good thing. — Scott Sauyet, Jul 27 '20 at 20:53
I support duplicate-closing in general but not how it's practiced on this site. I mentioned my last question. Also this question is specifically about algorithmic efficiency and Big O notation, yet was recommended to be closed in favor of a question that was not directly about that. — GirkovArpa, Jul 27 '20 at 20:54

score 1 · Accepted Answer · answered Jul 27 '20 at 20:50

1

Yes, use a Set for your DuplicateCheck which gives you O(1) access by id:

const duplicateCheck = new Set
const finalResult = []

for (const object of arrayOfObjects) {
    if (!duplicateCheck.has(object.id)) {
        duplicateCheck.add(object.id)
        finalResult.push(object)
    }
}

answered Jul 27 '20 at 20:50

Bergi

630,263
148
957
1,375

Shouldn't `new Set` be `new Set()`? Or are the parentheses optional these days? – 3limin4t0r Jul 27 '20 at 20:53
1

@3limin4t0r Parenthesis for constructor calls [have always been optional](https://stackoverflow.com/q/3034941/1048572) :-) – Bergi Jul 27 '20 at 20:54

msmolcic · Answer 2 · 2020-07-27T21:07:38.273

You could keep usedIds as object properties and add to the filtered array only if the object has no such property or just add your items in Set if that's a possibility for you. Set as a data structure can only store non-duplicates.

Without Set:

const filteredArray = [];
const usedIds = {};

for (const item of array) {
  if (!usedIds[item.id]) {
    usedIds[item.id] = true;
    filteredArray.push(item);
  }
}

With Set:

const filteredArray = [];
const usedIds = new Set();

for (const item of array) {
  if (!usedIds.has(item.id)) {
    usedIds.add(item.id);
    filteredArray.push(item);
  }
}

Runnable example:

const array = [
  {
    id: 1,
    stuff: 'stuff',
    moreStuff: 'moreStuff'
  },
  {
    id: 6,
    manyStuff: 'manyStuff',
    stuffing: 'stuffing'
  },
  {
    id: 4,
    yayStuff: 'yayStuff',
    stuff: 'stuff'
  },
  {
    id: 6,
    manyStuff: 'manyStuff',
    stuffing: 'stuffing'
  }
];

const filteredArray = [];
const usedIds = {};

for (const item of array) {
  if (!usedIds[item.id]) {
    usedIds[item.id] = true;
    filteredArray.push(item);
  }
}

console.log(filteredArray);

score 0 · Answer 3 · answered Jul 27 '20 at 20:55

You could iterate over the array and store the id in and object (hash table) and then check if exist. Something like:

const DuplicateCheck = {}
const FinalResult = []

for (let i = 0; i < ArrayOfObjects.length; i++) {
    let currentId = ArrayOfObjects[i].id

    if (!DuplicateCheck[currentId]) {
        DuplicateCheck[currentId] = 1
        FinalResult.push(ArrayOfObjects[i])
    }
}

And you will receive all unique objects in the FinalResult

3limin4t0r · Answer 4 · 2020-07-27T22:04:08.083

You can also use a Map to filter out duplicates. Contrary to the Set approach by Bergi this solution leaves the last version of the duplicate, since it overrides the key/value-pair with the same key.

const objectsById = new Map(arrayOfObjects.map(object => [object.id, object]));
const finalResult = Array.from(objectsById.values());

The code above does need to iterate the collection 2 times. Once using map to create key/value-pairs and once when the created array is converted to a Map.

When the resulting objectsById is created we'll have to iterate over the values to convert them back to array.

In total this means between 2 and 3 iterations over the full collection, which more often then not still a lot faster then solutions using find. Since that iterates over the array every time it is called.

You can reduce the amount of iterations by 1 if you omit the map call and manually insert the elements in objectsById:

const objectsById = new Map();
for (const object of arrayOfObjects) {
  objectsById.set(object.id, object);
}

What's a better algorithm to remove duplicates from an array of objects?

4 Answers4