How to combine 2 arrays so that each of them has elements from the other for O (n) complexity? I need that each object contain 1 element from another array, so we have 4 pair
let arr = [1,2]
let arr2 = ['first','second']
my solution with nested loops O(n^2)
const result = [];
for (let coachId of arr) {
for (let managerId of arr2)
result.push({ id1: coachId, id2: managerId });
}
expected result
[{id1: 1, id2: 'first'}, {id1: 1, id2: 'second'}, {id1: 2, id2: 'first'}, {id1: 2, id2: 'second'}]
As pointed out this won't reduce the time complexity of the full result, but you can use div & modulus to build up the result, this then avoids the double loop, and then you could use to reduce the time complexity of partial results, eg. paging data etc..
Out of curiosity did a quick benchmark doing this, and it is actually twice as fast too. But as pointed out in comments, it's more than likely the for of that's slows things down in your example, I assume there is a bit of overhead in JS creating the iterator for the array.
let arr = [1,2]
let arr2 = ['first','second']
const len = arr.length * arr2.length;
const result = new Array(len);
for (let p = 0; p < len; p += 1) {
result[p] = {
id1: arr[p / arr.length | 0],
id2: arr2[p % arr.length]
}
}
console.log(result);You can take advantage of Array.prototype.reduce to alter the shape of the array
let arr = [1,2]
let arr2 = ['first','second']
const result = arr.reduce((accumulator, current) => {
const obj = arr2.map(item => {
return {id1: current, id2: item};
});
return accumulator.concat(obj);
}, []);
console.log(result);Here is the process you start with performing a loop through the first array arr and for each item in that array you loop through each item in the second array arr2 and create an object with value from both Arrays
Here is what you could do in O(n) complexity, following would also handle case if your arrays aren't equal:
let arr = [1,2];
let arr2 = ['first','second','three'];
var res = [];
var maxLen = arr.length > arr2.length ? arr.length : arr2.length;
var i1=0;
var i2=0;
for(var i=0;i<maxLen;i++)
{
if(arr[i1])
{
res.push(arr[i1]);
i1++;
}
if(arr2[i2])
{
res.push(arr2[i2]);
i2++;
}
}