I am working on the CodeWars kata Array.diff:

Your goal in this kata is to implement a difference function, which subtracts one list from another and returns the result.

It should remove all values from list a, which are present in list b keeping their order.

arrayDiff([1,2],[1]) == [2]

If a value is present in b, all of its occurrences must be removed from the other:

arrayDiff([1,2,2,2,3],[2]) == [1,3]

My code:

function arrayDiff(a, b) {
  for(let i = 0; i<b.length; i  ){
    for(let j = 0; j<a.length; j  ){
      if(b[i]===a[j]){
        a.splice(j,1)
      }
    }
  }
  return a;
}

Somehow, although it works for most arrays, it doesn't give correct results for some arrays. Where exactly am I going wrong?

CodePudding user response：

Using splice on an array which you are iterating is tricky. By removing the current element from that array, the elements that came after it now appear at an index that is one less than where they were before, yet the loop variable will still be increased for the next iteration.

Moreover, this algorithm has a bad time complexity with its double loop over the whole range of indices.

You can do this in linear time: first create a Set so that it only retains unique values as they appear in the second array, and then filter the first array for values that don't appear in that set.

This idea is used in this spoiler:

function array_diff(a, b) { const remove = new Set(b); return a.filter( k => !remove.has(k) ); }