# 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? 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: