Imagine two arrays:
const array1 = [1,2,3];
const array2 = [2,3,4];
Now, I want to get all the differences of these two arrays and put them in two new arrays. One Array will be for all the items that where missing in the first. The other will be for the items missing in the second. The result would look something like this:
const newArray1 = [1];
const newArray2 = [4];
How would I go about this and what is the most efficient way?
const array1 = [2,1,3,5,2,1,3,5];
const array2 = [4,3,2,6,7,4,3,2,6,7];
function diff(arr1, arr2) {
const dontAddDuplicates = true;
arr1.sort();
arr2.sort();
let a1 = [];
let a2 = [];
let i = 0;
let j = 0;
while (i < array1.length || j < array2.length) {
if (i >= arr1.length) {
if (!dontAddDuplicates || (a2.length == 0 || a2[a2.length - 1] != arr2[j])) {
a2.push(arr2[j]);
}
j++;
} else if (j >= array2.length) {
if (!dontAddDuplicates || (a1.length == 0 || a1[a1.length - 1] != arr1[i])) {
a1.push(arr1[i]);
}
i++;
} else if (arr1[i] < arr2[j]) {
if (!dontAddDuplicates || (a1.length == 0 || a1[a1.length - 1] != arr1[i])) {
a1.push(arr1[i]);
}
i++;
} else if (arr2[j] < arr1[i]) {
if (!dontAddDuplicates || (a2.length == 0 || a2[a2.length - 1] != arr2[j])) {
a2.push(arr2[j]);
}
j++;
} else {
// Same value, do nothing
i++;
j++;
}
}
return [a1, a2];
}
console.log(diff(array1, array2));
// OUTPUT: [[1, 5], [4, 6, 7]]Here's another potential implementation using sorting, but it has the side effect of leaving array1 and array2 in a sorted fashion. Sorting allows you to avoid needing to rescan the other array every time. If they are already sorted then great you can skip this step. If the side effect is a problem, then use a deep copy of array1 and array2 before calling sort.
Flip dontAddDuplicates if you want duplicates or not. I notice the other implementations don't account for that, but easy enough to add.
Run time should be: SORT N + SORT M + N + M = SORT N = N LOG N depending on your input sizes and distributions SORT will be the significant O Notation https://www.bigocheatsheet.com/
https://jsfiddle.net/buscgtL2/1/
If you want to do it in N + M + N + M = N time you can use this implementation which uses a hash map instead of sorting. This has a disadvantage on memory space.
const array1 = [2,1,3,5,2,1,3,5];
const array2 = [4,3,2,6,7,4,3,2,6,7];
function diff(arr1, arr2) {
let dontAddDuplicates = true;
let a1 = [];
let a2 = [];
let a1hash = {};
let a2hash = {};
for (let i = 0; i < arr1.length; i++) {
a1hash[arr1[i]] = 0;
}
for (let i = 0; i < arr2.length; i++) {
a2hash[arr2[i]] = 0;
}
for (let i = 0; i < arr1.length; i++) {
if (!a2hash.hasOwnProperty(arr1[i])) {
if (!dontAddDuplicates || a1hash[arr1[i]] == 0) {
a1hash[arr1[i]] = 1;
a1.push(arr1[i]);
}
}
}
for (let i = 0; i < arr2.length; i++) {
if (!a1hash.hasOwnProperty(arr2[i])) {
if (!dontAddDuplicates || a2hash[arr2[i]] == 0) {
a2hash[arr2[i]] = 1;
a2.push(arr2[i]);
}
}
}
return [a1, a2];
}
console.log(diff(array1, array2));
//OUTPUT: [[1, 5], [4, 6, 7]]https://jsfiddle.net/2945y3an/1/
The worse performance would be any algorithm where for every N element you scan array M searching for a match. This would be N * M = N^2
You can achieve it in very simple way with minimum line of codes by using Array.filter() along with Array.includes() methods of JavaScript.
Working Demo :
const array1 = [1,2,3];
const array2 = [2,3,4];
const updatedArray1 = array1.filter(item => !array2.includes(item));
const updatedArray2 = array2.filter(item => !array1.includes(item));
console.log(updatedArray1); // [1]
console.log(updatedArray2); // [4]
Something like this would be relatively efficient, you're only iterating through two arrays.
Iterate through the first array and add any missing items to the first newArray. Repeat the same process for the second array.
If you need to only loop through the array once, you would need to do something similar to what is done below, but only loop through the longest array.
const array1 = [1,2,3];
const array2 = [2,3];
function diff (arr1, arr2) {
const newA1 = [];
const newA2 = [];
arr1.forEach((item, i) => {
let index = arr2.findIndex(it => it === item);
if(index < 0) newA1.push(item);
});
arr2.forEach((item, i) => {
let index = arr1.findIndex(it => it === item);
if(index < 0) newA2.push(item);
});
return [newA1, newA2];
}
console.log(diff(array1, array2));More efficent method (only loop through 1 array). This way you choose the longest array, loop through it, and check for duplicates of the current item of the long array and if an item in the secondary array exists at the same position, check for duplicates of this item in the longest array as well. This method is similar to the method above, but there is only 1 for each loop.
const array1 = [1,2,3];
const array2 = [3,4,5];
function diff (arr1, arr2) {
const newA1 = [];
const newA2 = [];
let baseArr, secondaryArr;
if(arr1.length > arr2.length) {
baseArr = arr1;
secondaryArr = arr2;
} else {
baseArr = arr2;
secondaryArr = arr1;
}
baseArr.forEach((item, i) => {
const secondaryArrI = secondaryArr.findIndex(it => it === item);
if(secondaryArrI < 0) newA1.push(item)
if(typeof secondaryArr[i] !== "undefined") {
const removeI = baseArr.findIndex(it => it === secondaryArr[i]);
if(removeI < 0) newA2.push(secondaryArr[i]);
}
})
return [newA1, newA2];
}
console.log(diff(array1, array2));
Lodash difference if you dot't mind
const array1 = [1,2,3];
const array2 = [2,3,4];
console.log(_.difference(array1, array2));
console.log(_.difference(array2, array1));.as-console-wrapper{min-height: 100%!important; top: 0}<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.21/lodash.min.js"></script>