Improving performance of the algorithm

Hi guys. Can I improve performance of this algorithm or it is the best solution?
The task is: Array C should contain all elements from arrA (maintaining the order) except those, that are present in arrB n times, where n is a prime number.

const isPrime = number => {
    for(let i = 2; i < number; i++)
      if(number % i === 0) return false;
    return number > 1;
  }

const countTimesInArr = (arr, val)=> arr.filter((item) => (item === val)).length;

const filterArr = (arrA, arrB) =>{
    let arrC = [];
    for(let i=0; i< arrA.length; i++){
        for(let j=0; j < arrB.length; j++){
            if(arrA[i] === arrB[j] || !arrA.includes(arrB[j])){
                if(!isPrime(countTimesInArr (arrB, arrB[j]))){
                    arrC.push(arrA[i]);
                    break;                     
                } 
                break;
            }            
        }
    }
    return arrC;
}
filterArr([2,3,9,2,5,1,3,7,10], [2,1,3,4,3,10,6,6,1,7,10,10,10]);

One improvement is it is not necessary to check all the way up to number. You can check up to the square root of number.

I came up with something like this:

const isPrime = number => {
    for(let i = 2; i < number; i++)
      if(number % i === 0) return false;
    return number > 1;
  }
const countTimesInArr = (arr, val)=> arr.filter((item) => (item === val)).length;

const filterArr= (arrA, arrB) =>{
    let primeCounts = [];
    for (let i = 0; i < arrB.length; i++) {
        if (isPrime(countTimesInArr(arrB, arrB[i]))) {
            primeCounts.push(arrB[i]);
        }
    }
    return arrA.filter(function(item) {
      return !(primeCounts.includes(item));
    });
}
filterArr([2,3,9,2,5,1,3,7,10], [2,1,3,4,3,10,6,6,1,7,10,10,10]);

The time complexity is O(n^2)? Am I counting correctly?

isPrime is O(n).
countTimesInArray is O(n)
filterArray, well, O(n) for the overall loop, which then runs isPrime (which is O(n) so O(n^2)), which runs countTimesInArray (which is also O(n) so O(n^4) I think?). That isn’t quite right, as I don’t think worst-case can cause it to do a full iteration all down the stack every time.
But then you run filter again which is O(n). So O(n + n^4) maybe? It is definitely not very efficient, though it may well do fine: you do a lot of iterations, it’s brute force.

This problem can be solved in linear time

Can you tell me how? :smiley:

You have to consider that O(m * n), where m is countable is still O(n). This is often seems counter intuitive, at least I couldn’t get it at first on my CS classes. So this would be linear time function:

filterArr(n) {
  linerTimeFunction1(n);
  linerTimeFunction2(n);
  linerTimeFunction3(n);
  ...
  linerTimeFunctionM(n);
  return n;
}

Taking this all into consideration, you can do following steps:

  1. Count occurrences of each number of Array B
  2. Convert values of resulting hash table into array
  3. Find max number of that array (max number of occurrences)
  4. Find all prime numbers up to max (storing them in hash table)
  5. Filter hash table from Step 1, leaving only those that present prime times
  6. Filter Array A, removing all values present as keys in hast table from Step 5

All these steps take linear time

Example:

arrA = [1, 2, 4, 6, 9];
objA = {
  1: 1,
  2: 2,
  4: 4,
  6: 6,
  9: 9
};

arrB = [1, 2, 3, 4, 5, 6];

arrB.filter(n => !arrA.includes(n)); // O(n^2)
arrB.filter(n => !objA[n]); // O(n)

Thank you @snigo.
I have problem with step 4.
How to make this without making nested loops?

You just run a loop of some kind over that object, and find the max value, and use a function for generating primes. Or you do something like this:

Object.keys(objA).filter((n) => isPrime(objA[n]));

Which will give you filtered version of those that are present in arrB n times, where n is a prime number. You would need to write a function that checked if a number was prime. Alternatively, just hardcode primes up to an arbitrary number. Then create a hash map of occurences. Then filter arrA based on whether each value does not have a prime number of occurences in ArrB.

For example (spoiler, but if the primes is the only bit you’re stuck on then this shouldn’t give anything away you don’t know):

function wierdFilter (targetArray, checkArray) { 
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);
  const occurences = {};

  for (const item of checkArray) {
    if (item in occurences) {
      occurences[item] += 1;
    } else {
      occurences[item] = 1;
    }
  };
  
  return targetArray.filter((item) => !(primes.has(occurences[item])));
}

There are couple O(n) algorithms for finding all primes up to n, search for JS implementation of any of these two, for example: