Home > Software design >  Delete all elements from an array A which are present in an array B without using a double loop
Delete all elements from an array A which are present in an array B without using a double loop

Time:04-24

So, as an input I have two arrays, A and B. Let's suppose that these are the values inside the two:

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and B = [1, 3, 5, 7, 9]

After the deletion the array A should be [2, 4, 6, 8, 10].

I have written (Javascript) this functioning algorithm to solve this problem:

for (var i=0; i < A.length; i  ) {
   for (var j=0; j < B.length; j  ) {
      if(B[j] == A[i]) 
         A.splice(i, 1) // Removes 1 element of the array starting from position i 
   }
}

I would like to know, is it possible to solve this problem without using a double loop?

CodePudding user response:

What about this:

let A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ;
const B = [1, 3, 5, 7, 9];

A = A.filter(num => !B.includes(num));

CodePudding user response:

Yes it is. You could use a Set. In terms of Set operations you are computing the difference A \ B.

Using a set which is optimized for lookups in O(1) time will speed up the computing the difference siginificantly from O(n²) when using includes() or double for loop to O(n).

const A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const B = [1, 3, 5, 7, 9]
const setB = new Set(B);
const difference = A.filter(x => !setB.has(x));
console.log(difference);

CodePudding user response:

Maybe that ?

const
  A = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
, B = [ 1, 3, 5, 7, 9 ]
  ;

for (let i = A.length, j= B.length -1 ; i-- ; )
  {
  if (A[i]===B[j]) { A.splice(i,1); j-- }
  }
  
document.write( JSON.stringify(A) )

  • Related