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