Array duplicate removal for duplicates exceeding `N`-number

Question

I recently encountered a front-end interview coding challenge question that required one to create a function which returned an array that excluded numbers that occurred more than n-number of times (i.e. duplicate-removal).In this example it was all numbers repeated >= three (3) times. I managed to submit an answer, but admittedly struggled solving it.

I am looking for any feedback / suggestions on how to make it more concise and efficient (the for loop inside the forEach method is especially repulsive).

Here is what I came up with:

// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const newArr = Array.from(arr).sort() let count = 0; let result = [] newArr.forEach((value, index, ar) => { count += 1; // refactored afterwards from (ar[index + 1] !== value) if (ar.lastIndexOf(value) <= index && count <= 2) { for (var i = 0; i < arr.length; i++) { if (arr[i] === value) { result.push(arr[i]) } } count = 0 } else if (ar[index + 1] !== value) { count = 0; } }); // +1 is there anyway to return a result that mimicks the original order of `numbers`? return result; // [1, 2, 2, 3, 4, 4] } // Ex. 1 const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));

Answer 1

As you expected, there is a much simpler way to do this.

1. Create a map where the keys are the numbers in the array and the value is the number of times each number appears in the array.
2. Filter the input array for any numbers that appear less than X times.

function removeMany(numbers, max) { const numberMap = numbers.reduce((map, num) => { map[num] = map[num] ? map[num] + 1 : 1; return map; }, []); return numbers.filter(num => numberMap[num] < max); } const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers, 3));

Answer 2

tl;dr

The code can be re-written to first count the number of occurrences of each number, then return an array filtering out any number that occurs more than 3 times.

// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const countMappings = arr.reduce(function(carry, item) { carry[item] = (carry[item] || 0) + 1; return carry; }, {}); return arr.filter(item => countMappings[item] < 3); } // Ex. 1 const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));

Suggestions

I was looking for any feedback / suggestions on how to make it more concise and efficient (the for loop inside the forEach method is especially repulsive).

The original code already uses functional techniques - i.e. array.forEach()- for one loop. Perhaps you are already familiar with functional techniques like that and others but if not, I recommend going through these exercises.

That inner for loop can be re-written using array.forEach():

arr.forEach(function(element, i) { //for (var i = 0; i < arr.length; i++) { if (element === value) { result.push(element); } }); 

// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const newArr = Array.from(arr).sort() let count = 0; let result = [] newArr.forEach((value, index, ar) => { count += 1; // refactored afterwards from (ar[index + 1] !== value) if (ar.lastIndexOf(value) <= index && count <= 2) { arr.forEach(function(element, i) { //for (var i = 0; i < arr.length; i++) { if (element === value) { result.push(element); } }); count = 0 } else if (ar[index + 1] !== value) { count = 0; } }); // +1 is there anyway to return a result that mimicks the original order of `numbers`? return result; // [1, 2, 2, 3, 4, 4] } // Ex. 1 const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));

For that commented line:

// +1 is there anyway to return a result that mimicks the original order of numbers?

One approach to handle that would be to iterate over the elements using array.reduce() (so we can conditionally add values to the output array), counting the occurrences of each element, then in a second iteration, only return elements where there are 2 or less occurrences of that element.

One main advantage here compared to the original is that there is not a nested iteration... the complexity is \$O(n)\$ instead of \$O(n^2)\$.

See the example below. I wanted to compare with jsPerf but that appears to be down. I did find a similar system: measurethat.net - see the comparison here.

// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const countMappings = arr.reduce(function(carry, item) { if (carry[item]!== undefined) { carry[item]++; } else { carry[item] = 1; } return carry; }, {}); return arr.reduce(function(final, item) { if (countMappings[item] <3) { final.push(item); } return final; }, []); } // Ex. 1 const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));

Edit

Bravo to Gerrit0 for using Array.filter() and having very concise code! The performance results appear to be similar.

Utilizing filter() instead of reduce for the second iteration can eliminate a few lines:

return arr.reduce(function(final, item) { if (countMappings[item] <3) { final.push(item); } return final; }, []); 

becomes:

return arr.filter(function(item) { return countMappings[item] < 3; }); 

Or if you want to use ES-6 arrow functions:

return arr.filter(item => countMappings[item] < 3); 

Additionally, the first iteration, to count the occurrences of each element, could be simplified using a ternary operator:

const countMappings = arr.reduce(function(carry, item) { if (carry[item]!== undefined) { carry[item]++; } else { carry[item] = 1; } return carry; }, {}); 

becomes:

const countMappings = arr.reduce(function(carry, item) { carry[item] = carry[item]? carry[item] + 1: 1; return carry; }, {}); 

Or as was suggested in comments, use logical OR:

carry[item] = (carry[item] || 0) + 1; 

to implicitly check if carry[item] has a value - if not, use 0 before incrementing the count for the value of the given element.

// Remove duplicates that occur 3 or more times in an array // keeping unique values and those with less than 3 function removeMany(arr) { const countMappings = arr.reduce(function(carry, item) { carry[item] = (carry[item] || 0) + 1; return carry; }, {}); return arr.filter(item => countMappings[item] < 3); } // Ex. 1 const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5]; console.log(removeMany(numbers));