Merge two arrays avoiding O(n^2) complexity

Question

Given two arrays, farmers and collections, I want to be able to merge the farmer information to each collection when farmer_id in the collection is equal to id in farmers. if there is no id of the farmer that matches farmer_id in the collection then that collection should have a an empty farmer object

const farmers = [{
        id: 10,
        name: 'John Doe',
        email: 'jdoe@gmail.com'
    },
    {
        id: 11,
        name: 'James Bond',
        email: 'james@gmail.com'
    }
]

const collections = [{
        id: 9,
        name: 'Book',
        farmer_id: 10,
        date: 'June'
    },
    {
        id: 10,
        name: 'Game',
        farmer_id: 11,
        date: 'July'
    },
    {
        id: 13,
        name: 'Car',
        farmer_id: 10,
        date: 'August'
    },
    {
        id: 11,
        name: 'Wristwatches',
        farmer_id: 20,
        date: 'August'
    }
]

The result should be in this format below

const result = [{
        id: 9,
        name: 'Book',
        farmer_id: 10,
        date: 'June',
        farmer: {
            id: 10,
            name: 'John Doe',
            email: 'jdoe@gmail.com'
        }
    },
    {
        id: 10,
        name: 'Game',
        farmer_id: 11,
        date: 'July',
        farmer: {
            id: 11,
            name: 'James Bond',
            email: 'james@gmail.com'
        }
    },
    {
        id: 13,
        name: 'Car',
        farmer_id: 10,
        date: 'August',
        farmer: {
            id: 10,
            name: 'John Doe',
            email: 'jdoe@gmail.com'
        }
    },
    {
        id: 11,
        name: 'Wristwatches',
        farmer_id: 20,
        date: 'August',
        farmer: {}
    }
]

This is what i have been able to come up with but am stuck right now

function mapper(farmers, collectors) {
    for (let k = 0; k < farmers.length; k++) {
        const idToFarmerInfo = {};
        idToFarmerInfo[farmers[k].id] = farmers[k];
        for (let j = 0; j < collectors.length; j++) {
            let mapper = idToFarmerInfo[collectors[j].farmer_id];
            farmers[mapper] = collectors[j]
        }
    }
    return farmers
}

i followed this link as am trying to avoid O of N squared but O of N complexity

Answer 1

You can create a Map collection to have O(N) of access to desired farmer by id. Then mapping becomes faster in terms of performance:

const unique = new Map(farmers.map(f=> [f.id, f]));

const result = collections.map(s => ({
    ...s, farmer_id: unique.get(s.farmer_id) || s.farmer_id
}))

Now mapping of collections has complexity O(N). However, do not forget to sum complexity of making unique farmers. The overall complexity is O(N) + O(M).

An example:

const farmers = [{
    id: 10,
    name: 'John Doe',
    email: 'jdoe@gmail.com'
},
{
    id: 11,
    name: 'James Bond',
    email: 'james@gmail.com'
}
];

const collections = [{
    id: 9,
    name: 'Book',
    farmer_id: 10,
    date: 'June'
},
{
    id: 10,
    name: 'Game',
    farmer_id: 11,
    date: 'July'
},
{
    id: 13,
    name: 'Car',
    farmer_id: 10,
    date: 'August'
},
{
    id: 11,
    name: 'Wristwatches',
    farmer_id: 20,
    date: 'August'
}
];

const unique = new Map(farmers.map(f=> [f.id, f]));

const result = collections.map(s => ({
    ...s, farmer_id: unique.get(s.farmer_id) || s.farmer_id
}))

console.log(result);

Answer 2

Demo on stackblitz

You can use a more declarative approach and use Array.map and Array.find

const result = collections.map(collection => {
  return {
    ...collection,
    farmer: farmers.find(farmer => collection.farmer_id == farmer.id) || {}
  };
});

console.log(result);

Answer 3

For a better performance you could create a hash of farmers where the complexity is O(N) because we're iterating the farmers list only once.

const farmers = [{ id: 10, name: 'John Doe', email: 'jdoe@gmail.com' }, { id: 11, name: 'James Bond', email: 'james@gmail.com' } ]; const collections = [{ id: 9, name: 'Book', farmer_id: 10, date: 'June' }, { id: 10, name: 'Game', farmer_id: 11, date: 'July' }, { id: 13, name: 'Car', farmer_id: 10, date: 'August' }, { id: 11, name: 'Wristwatches', farmer_id: 20, date: 'August' } ]

var farmers_hash = farmers.reduce((hash, item) => {
  hash[item.id] = item;
  return hash;
}, {});

console.log(farmers_hash);

The following step is to build the desired output by assigning one farmer using hash keys.

This can be achieved using map method in combination with Object.assign.

const farmers = [{ id: 10, name: 'John Doe', email: 'jdoe@gmail.com' }, { id: 11, name: 'James Bond', email: 'james@gmail.com' } ]; const collections = [{ id: 9, name: 'Book', farmer_id: 10, date: 'June' }, { id: 10, name: 'Game', farmer_id: 11, date: 'July' }, { id: 13, name: 'Car', farmer_id: 10, date: 'August' }, { id: 11, name: 'Wristwatches', farmer_id: 20, date: 'August' } ]

var farmers_hash = farmers.reduce((hash, item) => {
  hash[item.id] = item;
  return hash;
}, {});

var result = collections.map((item) => {
  item.farmer = Object.assign({}, farmers_hash[item.farmer_id])
  return item;
});

console.log(result);

As you can see the final complexity is O(N) + O(M) where N is the length of farmers array and M is the length of collections array.