Changing an array in place using splice()

Question

I'm trying to write a function that, given an array and n, returns the array with elements repeating no more than n times. I cannot change the order of the array.

Below is the code I have so far. What is perplexing me is that it works for most elements in a given array, but not for some others. I'm trying to find a rhyme or reason for the elements for which the code does not work.

function deleteNth(arr,n){
  arr.forEach(function (item, index) {
    var count = 0;
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] === item) {
        count++;
      while (count > n) {
       var remove = arr.lastIndexOf(item);
       arr.splice(remove, 1);
       count--;
      }
    }
  }
});
  return arr;
}


var x = deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 
35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 
35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 
2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2);

console.log(x);

Currently returns this...

[7, 26, 21, 41, 43, 2, 26, 24, 10, 10, 10, 24, 35, 35, 43, 41, 7, 21, 
41, 2, 43, 28]

But I should get this...

[7, 26, 21, 41, 43, 2, 26, 24, 10, 10, 24, 35, 35, 43, 41, 7, 21, 2, 
28]

Any insight into where I'm going wrong would be sincerely appreciated.

Answer 1

The logic of where you places the while loop is wrong, you need to place it outside of the for loop.

function deleteNth(arr, n) {
  arr.forEach(function(item, index) {
    var count = 0;
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] === item) {
        count++;        
      }
    }
    while (count > n) {
      var remove = arr.lastIndexOf(item);
      arr.splice(remove, 1);
      count--;
    }
  });
  return arr;
}


var x = deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35,
  35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41,
  35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7,
  2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10
], 2);

console.log(x);

Why? Because when you are doing your loop and you remove things from it, you shift things back down. So when you have two items side by side and you remove the first the second one shifts down one spot to fill what you just removed. The i does not change so you do not check the item that just filled the gap.

What would I do? I would just keep track of the items as I get to it and if I have not gone over the max append it.

function cleanUp (arr, max) {
  const cnts = {}  // keep track of what we find
  return arr.reduce((a, i) => { // loop over the array index by index
    cnts[i] = (cnts[i] || 0) + 1;  // mark that I seen the number
    if (cnts[i] <= max) {  // check to see if we are under the max
      a.push(i)  //if we are, add it to an arry
    }
    return a  // return the array for reduce
  }, [])
}
console.log(cleanUp([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 
35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 
35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 
2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2))

Answer 2

This code works:

function deleteNth(arr,n){
     var rem = new Array(), new_arr = new Array();
     arr.forEach(function (item, index) {
        if(!rem[item]) rem[item]=0;
     	if(rem[item]<n){
        	new_arr.push(item);
        	rem[item]++;
        }
     });
    return new_arr;
   }

console.log(deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2));

Answer 3

All of your code is true. Just bring that while out of for loop.

function deleteNth(arr, n) {
  arr.forEach(function(item, index) {
    var count = 0;
    for (var i = 0; i < arr.length; i++) {
      if (arr[i] === item) {
        count++;
      }
    }
    while (count > n) {
          var remove = arr.lastIndexOf(item);
          arr.splice(remove, 1);
          count--;
        }
  });
  return arr;
}


var x = deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35,
  35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41,
  35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7,
  2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10
], 2);

console.log(x);

Answer 4

I like Nina's filter (probably performs better as well) but you can also use reduce:

function deleteNth(arr,n){
  return arr.reduce(
    ([result,map],item)=>{
      const count = (map.get(item)||0)+1;
      return [
        //do not add if more than n of this item have been added already
        (count<=n)?result.concat(item):result,
        map.set(item,count)//set the new count for this item and return map
      ]
    },
    [[],new Map()]//initial value for result and map
  )[0];
}

Here is an example using filter and a Map:

function deleteNth(arr,n){
  const map = new Map();
  return arr.filter(
    item=>{
      const count = (map.get(item)||0)+1;
      map.set(item,count);
      return (count<=n);
    }
  );
}
console.log(deleteNth([1,2,3,2,4,2,5], 2));

Answer 5

If you really want to do it in place, then this answer is not for you. (I think there are very good reasons to work with immutable data, but if you want to mutate, one of the other answers should do it.

Here's one solution that simply keeps a count of each item seen as you go, and filters out those we've seen too often:

const deleteNth = (arr, n) => {
  const found = new Map()
  return arr.filter(val => {
    found.set(val, (found.get(val) || 0) + 1)
    return found.get(val) <= n
  })
}

const result = deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2)

console.log(result)

One other note: It might offer a nicer API if you choose:

deleteNth = (n) => (arr) => { /* ... */ }

This way you could pass just the repetition count and get back a new function which filters an array.

(Also, this does not sound like a good name for something that delete's all repetitions of a value after the nth one.)

Answer 6

For a fast mutating version, you could use a single while loop, a hash table for counting the items and an adjustment of the index if a splice happens.

function deleteNth(array, n) {
    var counter = Object.create(null),
        i = 0, v;

    while (i < array.length) {
        v = array[i];
        if (!counter[v]) {
            counter[v] = 0;
        }
        if (++counter[v] > n) {
            array.splice(i, 1);
            continue;
        }
        i++;
    }
    return array;
}

console.log(deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

A better way is to use filter and return a new array.

function deleteNth(array, n) {
    var counter = Object.create(null);
    return array.filter(v => (counter[v] = (counter[v] || 0) + 1) <= n);
}

console.log(deleteNth([7, 26, 21, 41, 43, 2, 26, 24, 10, 26, 10, 10, 24, 35, 35, 35, 43, 26, 41, 7, 24, 24, 21, 24, 10, 35, 10, 7, 24, 7, 35, 26, 41, 35, 2, 43, 24, 2, 41, 26, 41, 7, 7, 26, 2, 10, 43, 10, 35, 41, 24, 7, 2, 2, 7, 2, 26, 24, 26, 43, 43, 21, 10, 28, 10], 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }