I'm solving the problem of finding the common numbers in two arrays.
My first approach was:
const findCommonNumbers = (array1,array2) => {
const map = array1.reduce((accum, element)=>{
accum[element] = true;
return accum;
} , {});
const result = [];
array2.forEach((e)=>{
if (map[e]) {
result.push(e);
}
});
return result;
}
const array1 = [4, 2, 3, 6, 23];
const array2 = [3, 2, 4, 7 ,9];
const result = findCommonNumbers(array1, array2 );
console.log('result', result);
But then, looking at the solution, the most efficient way seems to be:
const findCommonNumbers = (array1, array2) => {
const result = [];
let p1 = 0;
let p2 = 0;
while (p1 < array1.length && p2 < array2.length) {
const e1 = array1[p1];
const e2 = array2[p2];
if (e1 === e2) {
result.push(e1);
p1++;
p2++;
}
else if (e1 < e2) {
p1++;
}
else {
p2++;
}
}
return result;
}
const array1 = [2, 3, 4, 6, 23];
const array2 = [2, 3, 4, 7, 9];
const result = findCommonNumbers(array1, array2);
console.log('result', result);
But, I see that in both cases, both arrays are iterated once, besides, my initial solution also works for unsorted arrays. What would be the complexity of both algorithms, and why? Is the proposed solution more efficient just by the fact that both arrays are iterated in the same loop, while in my case I iterate them sequentially?
