Compare two arrays of objects and get the objects based on ids

Question

I have two arrays of objects. One has an id property with a list of ids and the second has an object with a unique id property. I want to filter the ids in the second array with the first list and get the data.

const data1 = [{
 name: 'A',
 ids: [1, 2, 3]
}, {
 name: 'B',
 ids: [4, 5, 6]
}, {
 name: 'C',
 ids: [7, 8, 9]
}]
const data2 = [{
 id: 1,
 color: 'red'
 }, {
 id: 2,
 color: 'black'
 }, {
 id: 3,
 color: 'blue'
 }, {
 id: 4,
 color: 'yellow'
 }, {
 id: 5,
 color: 'green'
 }, {
 id: 6,
 color: 'pink'
 },
 {
 id: 7,
 color: 'orange'
 }, {
 id: 8,
 color: 'white'
 }, {
 id: 9,
 color: 'teal'
 }
]
const arrayToObject = (array) =>
 array.reduce((obj, item) => {
 obj[item.id] = item
 return obj
 }, {})
console.log(arrayToObject(data2))
const newData = data1.map(item => {
 return {
 name: item.name,
 data: item.ids.map(i => arrayToObject(data2)[i])
 }
})
console.log(newData)

Expected Output:

[
 {
 "name": "A",
 "data": [
 {
 "id": 1,
 "color": "red"
 },
 {
 "id": 2,
 "color": "black"
 },
 {
 "id": 3,
 "color": "blue"
 }
 ]
 },
 {
 "name": "B",
 "data": [
 {
 "id": 4,
 "color": "yellow"
 },
 {
 "id": 5,
 "color": "green"
 },
 {
 "id": 6,
 "color": "pink"
 }
 ]
 },
 {
 "name": "C",
 "data": [
 {
 "id": 7,
 "color": "orange"
 },
 {
 "id": 8,
 "color": "white"
 },
 {
 "id": 9,
 "color": "teal"
 }
 ]
 }
]

I did manage to achieve this, but I guess there might be a better clean and performant solution. Please advice me on that.

P.S: I am also open to using lodash.

Answer 1

Use Map to reduce search complexity

Currently your method is rather complex at \$O(n^2)\$. The reason is that for each Id you iterate each item to locate the one with the Id you want.

You can use a Map to reduce the complexity. Map uses a hash to locate items, you can add each id to a map linking ids to each category.

Then just iterate the items array using the map to locate the correct category and add the item.

The result is achieved in a time complexity of \$O(n)\$.

The example shows how this can be implemented.

const categories = [{name: 'A', ids: [1, 2, 3]}, {name: 'B', ids: [4, 5, 6]}, {name: 'C', ids: [7, 8, 9]}]
const items = [{ id: 1, color: 'red'}, { id: 2, color: 'black'}, { id: 3, color: 'blue'}, { id: 4, color: 'yellow'}, { id: 5, color: 'green'}, { id: 6, color: 'pink'},{ id: 7, color: 'orange'}, { id: 8, color: 'white'}, { id: 9, color: 'teal'}];
function categorizeById(cats, items) {
 const idMap = new Map();
 const result = cats.map(cat => {
 const category = {name: cat.name, data: []};
 cat.ids.forEach(id => idMap.set(id, category));
 return category ;
 },[]);
 items.forEach(item => idMap.get(item.id).data.push({...item}));
 return result;
}
console.log(categorizeById(categories, items));