Find missing element by comparing 2 arrays in Javascript

Question

For some reason, I had serious difficulties with this problem. I need this JS function that takes 2 arrays, compares 2, and then returns the row of the missing element. For instance. Find the element that is not in the currentArray that was there in the previous array.

function findDeselectedItem(CurrentArray, PreviousArray){ var CurrentArrSize = CurrentArray.length; var PrevousArrSize = PreviousArray.length; // Then my brain gives up on me... // I assume you have to use for-loops, but how do you compare them?? return missingElement; } 

Thanks in advance! I am not asking for the code, but even just a push in the right direction or a hint may help ...

Answer 1

That should work. You should also consider the case where the elements of arrays are also arrays. Then indexOf may not work as expected.

 function findDeselectedItem(CurrentArray, PreviousArray) { var CurrentArrSize = CurrentArray.length; var PreviousArrSize = PreviousArray.length; // loop through previous array for(var j = 0; j < PreviousArrSize; j++) { // look for same thing in new array if (CurrentArray.indexOf(PreviousArray[j]) == -1) return PreviousArray[j]; } return null; } 

Answer 2

Description of the problem:

Find the element that is not in the current array that was there in the previous array.

 previousArray.filter(function(x) { // return elements in previousArray matching... return !currentArray.includes(x); // "this element doesn't exist in currentArray" }) 

(This is just as bad as writing two nested for loops, i.e. O (N ² ). This can be made more efficient, if necessary, by creating a temporary object from currentArray , and using it as a hash table for O ( 1) requests. For example :)

 var inCurrent={}; currentArray.forEach(function(x){ inCurrent[x]=true }); 

So, we have a temporary search table, for example.

 previousArray = [1,2,3] currentArray = [2,3]; inCurrent == {2:true, 3:true}; 

Then the function does not need to repeatedly search for the current Array each time, which would be the O (N) approach; it can instantly check if it is in currentArray O (1) times. Since .filter is called N times, this results in a total time of O (N), not O (N ² ):

 previousArray.filter(function(x) { return !inCurrent[x] }) 

Alternatively, here is the style for the loop:

 var inCurrent = {}; var removedElements = [] for(let x of currentArray) inCurrent[x] = true; for(let x of previousArray) if(!inCurrent[x]) removedElements.push(x) //break; // alternatively just break if exactly one missing element console.log(`the missing elements are ${removedElements}`) 

Or just use modern data structures that make the code more obvious:

 var currentSet = new Set(currentArray); return previousArray.filter(x => !currentSet.has(x)) 

Answer 3

Take a look at the underscore difference feature: http://documentcloud.github.com/underscore/#difference

Answer 4

I know this is code, but try to see examples of differences to figure out a way:

 var current = [1, 2, 3, 4], prev = [1, 2, 4], isMatch = false, missing = null; var i = 0, y = 0, lenC = current.length, lenP = prev.length; for ( ; i < lenC; i++ ) { isMatch = false; for ( y = 0; y < lenP; y++ ) { if (current[i] == prev[y]) isMatch = true; } if ( !isMatch ) missing = current[i]; // Current[i] isn't in prev } alert(missing); 

---

Or using ECMAScript 5 indexOf :

 var current = [1, 2, 3, 4], prev = [1, 2, 4], missing = null; var i = 0, lenC = current.length; for ( ; i < lenC; i++ ) { if ( prev.indexOf(current[i]) == -1 ) missing = current[i]; // Current[i] isn't in prev } alert(missing); 

And since

 var current = [1, 2, 3, 4], prev = [1, 2, 4], missing = null, i = current.length; while(i) { missing = ( ~prev.indexOf(current[--i]) ) ? missing : current[i]; } alert(missing); 

Answer 5

This is my approach (also works for duplicate entries): - // here the second argument is the current array

 function(previousArray, currentArray) { var hashtable=[]; //store occurances of elements in 2nd array in hashtable for(var i in currentArray){ if(hashtable[currentArray[i]]){ hashtable[currentArray[i]]+=1; //add 1 for duplicate letters }else{ hashtable[currentArray[i]]=1; //if not present in hashtable assign 1 } } for(var i in previousArray){ if(hashtable[previousArray[i]]===0 || hashtable[previousArray[i]] === undefined){ //if entry is 0 or undefined(means element not present) return previousArray[i]; //returning the missing element } else{ hashtable[previousArray[i]]-=1; //reduce count by 1 } } } 

The logic is that I created an empty array called hashtable. We first iterate through currentArray and use the elements as index and values ​​as counters starting at 1 (this helps in situations where there are duplicate entries). Then we iterate through the previousArray and look for indexes, if they match, we decrease the value of count by 1. If the element of the 2nd array does not exist at all, then the undefined check condition is satisfied, and we return it. If duplicates exist, they are reduced by 1 each time and when 0 is encountered, this elment is returned as a missing element.