CODEWITHSUNDEEP
javascriptarraysfilter
CarlssonK
CarlssonK

Reputation: 156

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

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

Upvotes: 0

Views: 67

Answers (2)

marcobiedermann
marcobiedermann

Reputation: 4915

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

Upvotes: 1

Giorgi Moniava
Giorgi Moniava

Reputation: 28654

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

let map = {};

array.forEach(x => {
    map[x.id] = (map[x.id] || 0) + 1
});

console.log(array.filter(x => map[x.id] === 1))

Upvotes: 1

Related Questions