Remove items from one array if not in the second array?

Question

I state that I have tried for a long time before writing this post. For an InDesign script, I'm working with two array of ListItems. Now I'm trying to remove the items of one array that aren't in the second array, but i'm stuck. Given that I use the following javascript code (it works great) to remove the equal items between the two arrays : function check_dupli(arr_A, arr_B) { for(var i = arr_B.length - 1; i >= 0; i--) { for(var j = 0; j < arr_A.length; j++) { if(arr_B[i] === arr_A[j]) { arr_B.splice(i, 1); } } } arr_B.sort(); } arr_A = ["a","b","d","f","g"] arr_B = ["a","c","f","h"] check_dupli(arr_A, arr_B) --> arr_B = ["c","h"] check_dupli(arr_B, arr_A) --> arr_B = ["b","d","g"] I thought to modify it in order to ignore the items not that are not in both arrays, and to obtain what I want, but something is going wrong because I also get the unwanted data : function get_dupli(arr_A, arr_B, arr_C) { for(var e = arr_B.length - 1; e >= 0; e--) { for(var k = 0; k < arr_A.length; k++) { if(arr_B[e] === arr_A[k]) { arr_C.push(arr_B[e]); } } } arr_C.sort(); } arr_A = ["a","b","d","f","g"] arr_B = ["a","g","k"] arr_C = ["h"] get_dupli(arr_A, arr_B, arr_C) --> arr_C = ["a","g","h","k"] instead of --> ["a","g","h"] get_dupli(arr_B, arr_A, arr_C) --> arr_C = ["a","b","d","f","g","h"] instead of --> ["a","g","h"] Where I'm wrong? There is another way in pure javascript to solve the problem? Thanks in advance for any help.

Answer 1

There are several ways to find duplicates between two arrays. The naive approach is to loop over either array and use the "indexOf" method on the other array to check if that array has the current element in the loop. If it does, just push it to an array that stores the duplicates as such:

function getDuplicates(arrOne, arrTwo) {

var duplicates = [];

for (let i=0; i<arrOne.length; i++) {

if (arrTwo.indexOf(arrOne[i]) !== -1) {

duplicates.push(arrOne[i]);

}

}

return duplicates;

}

getDuplicates(["a","b","d","f","g"], ["a","c","f","h"]);

There are some caveats to this approach though that you need to be aware of:

1. Since "indexOf" performs a loop on array inside the loop (it is basically a nested loop), this code runs in O(n^2) time (quadratic time). This means that for each item in the outer array there is a check on every item in the inner array. This can be very expensive if you are comparing large arrays, say each with 1000 items (you would have 1000 * 1000 passes, or 1,000,000). If you are using this function to solve a little problem once for two small arrays like the ones in your question this shouldn't be an issue but you should avoid nested loops if you can (and in this case you can as you shall see below).
2. This function will only work accurately if you have one instance of each item in each array. For instance, if "arr1 = [a,b,d,f,f,f]" and "arr2 = [a,b,c,d,e,f]" you will yield two different results depending on which array you put in the "for loop". If you loop over arr1 you will have these letters as duplicates: a,b,f,f,f but if you loop over arr2 you have a,b,f. Again, depending on the data you are working with this might work, but it WON'T WORK FOR ALL CASES.

I thought it was important to give you that "solution" because it may work for your specific case. Now that that is out of the way we can look into a more robust approach. The next algorithm used to solve the problem is known as frequency counter pattern (I don't think it is an official name, but it is known as such),

In this algorithm you can use an object to store the element and its count (how many there are, say a: 2, b: 3, etc) from one array and and then check if that element is in the other array. If it is, push that element to an array that stores the duplicates and decrease the count of that item in the object--say "a" is a duplicate and you have "a: 2" in the object; after you push "a" to the duplicates array you subtract one from is value in the object ("a: 1"); if the value is 0 you delete that property from the object.

This would be the code:

function getDuplicates(arrOne, arrTwo) {

var duplicates = [];

var freqCounterOne = {};

// loop over arrOne

for (let i=0; i<arrOne.length; i++) {

// if the item is in the object, increment its value

// if it is not, initialize it to 1

freqCounterOne[arrOne[i]] = ++freqCounterOne[arrOne[i]] || 1;

}

// loop over arrTwo

for (let i=0; i<arrTwo.length; i++) {

let currItem = arrTwo[i];

// if currItem's value > 0

if (freqCounterOne[currItem]) {

duplicates.push(currItem);

// decrement value by 1

freqCounterOne[currItem]-=1;

}

}

return duplicates;

}

getDuplicates(["a","c","f","f", "h"] , ["a","b","d","f","f", "f", "g"]);

This code runs in linear time O(n). Although it seems like it does more work, it is much faster than the first algorithm because it doesn't have the nested loop. This code will work for every case scenario where you want ALL duplicates, so in the case above you would have ["a", "f", "f"] regardless of which array you use in the first or second loops.

I hope this helps.