6

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.

Improve this question
6
  • The way you are attacking it seems like a bad way to do it. A simple loop where you keep track of what is used and append to a new array would seem like a better approach. A lot less looping. Commented May 16, 2018 at 18:20
  • What is the value of n? Commented May 16, 2018 at 18:20
  • @NicholasMansfield In the out put example above, n = 2. Commented May 16, 2018 at 18:22
  • 1
    @epascarello I think you're right. I just thought there'd be value in figuring out why this one doesn't work, since it seems like it should. Commented May 16, 2018 at 18:24
  • 1
    A function that mutates the input can explicitly return undefined, that is a good way to indicate impure function. You can return a new array with the modifications and leave the input untouched. Commented May 16, 2018 at 18:26

6 Answers 6

Reset to default
4

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))

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Ohhh, I see. That's exactly what I was trying to figure out (the first block of code you wrote). I definitely take your point about creating a new array instead of changing the original. Thanks for the help!
You can .concat instead of .push to make the reduce niftier.
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));

Improve this answer

1 Comment

This method is more efficient
2

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);

Improve this answer

1 Comment

Thanks, Saeed. I appreciate that your feedback!
2

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));
Improve this answer

Comments

2

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.)

Improve this answer

3 Comments

Thanks, Scott. This seems like an efficient solution. I'm not glued to the idea of changing in place--just a beginner trying to get a good grip on the basics. As for the name, I agree, but Codewars wants the name it created itself :)
Ahh, CodeWars. It's been a while! Best of luck. If you like this idea, look at Nina's solution. It's a bit cleaner than mine.
I'll do that! Thanks again!
2

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; }

Improve this answer

5 Comments

Both of these solutions return arrays with more than two 10s in them.
@ScottSauyet, sorry missed that.
Well, the second one is fixed. An exception now in the first.
This filter (with an Object, not a Map) is definitely nicer than mine.
Thanks a lot, Nina. Love the brevity of this second one.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.