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
– Dave S, Commented Jul 27, 2020 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
– GirkovArpa, Commented Jul 27, 2020 at 20:44
Does this answer your question? Remove duplicates from an array of objects in JavaScript — Heretic Monkey
– Heretic Monkey, Commented Jul 27, 2020 at 20:44
I don't get points for closing questions as a dupe. You'd know that if you read the privileges page instead of going with your prejudices. Also, you're not the OP @GirkovArpa, so why are you even responding? — Heretic Monkey
– Heretic Monkey, Commented Jul 27, 2020 at 20:49
@GirkovArpa: Removing duplicate questions is a community service, earning no reputation points or other rewards. — Scott Sauyet
– Scott Sauyet, Commented Jul 27, 2020 at 20:50

Bergi · Accepted Answer · 2020-07-27 20:50:02Z

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, 2020 at 20:50

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

3limin4t0r Over a year ago

Shouldn't new Set be new Set()? Or are the parentheses optional these days?

Bergi Over a year ago

@3limin4t0r Parenthesis for constructor calls have always been optional :-)

Stanimir Georgiev · Accepted Answer · 2020-07-27 20:55:33Z

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

msmolcic · Accepted Answer · 2020-07-27 21:07:38Z

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);

3limin4t0r · Accepted Answer · 2020-07-27 22:04:08Z

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);
}

Collectives™ on Stack Overflow

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

4 Answers 4

2 Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Linked

Related