Efficient way to get unique objects from array of objects, by object property?

Question

Here is my array of objects

const array = [ 
  {id: 1, data: "foo"}, 
  {id: 1, data: "bar"}, 
  {id: 2, data: "baz"} 
]

I want to remove all duplicate objects by its id and return only the array of objects that have an unique id.

Expected result:

[ 
  {id: 2, data: "baz"} 
]

This is what I have now: O(n^2)

function getUnique(array) {
    const newArray = []

    for (let obj of array) {
        if (array.filter(x => x.id === obj.id).length === 1) {
            newArray.push(obj)
        }
    }

    return newArray
}

Whats the more efficient way to achieve this?

Is it possible to get the time-complexity to O(n) or O(n log n)?

Answer 1

I would suggest to count the number of occurrences in your array and store them in a Map. Next you filter all element, which count is 1

function getUnique(arr) {
  const count = new Map();

  arr.forEach((element) => {
    count.set(element.id, (count.get(element.id) || 0) + 1);
  });

  return array.filter((element) => {
    return count.get(element.id) === 1;
  });
}

This has a runtime of 2(n) since you have to iterate over them twice