How to remove objects from an array most efficiently?

Question

I am wondering if I can rearrange an array faster when I would like to delete more than one object.

You are given a List:

• 1
• 2
• 2
• 3
• 4
• 5
• 7

And now you want to delete every "2" in the list. So what I would do, is:

int size = 7;
int array[size] = {1,2,2,3,4,5,7};
for(int i = size-1; i >= 0; i--){
   if(array[i] == 2){
      memcpy(&array[i],&array[i+1], size-i);
      size--;
   }
}

But this is not a efficent way doing so, is it? So I wonder if I could do this on a smarter way without allocating extra memory.

Answer 1

You can maintain a pointer that, in the $i$th iteration, points to the $i$th element that is not 2, i.e., the $i$th element in the final array. In each iteration, we only move the element to which the pointer points to the $i$th position.

int size = 7;
int array[7] = {1,2,2,3,4,5,7};
int i = -1;
int p = -1;
while (1)
{
    ++i;
    do ++p; while (p < size && array[p] == 2);
    if (p >= size) break;
    array[i] = array[p];
}
size = i;

In your example, it works as follows.

Initial: 1 2 2 3 4 5 7
After the 1st iteration: 1 2 2 3 4 5 7
                         i
                         p

After the 2nd iteration: 1 3 2 3 4 5 7
                           i   p

After the 3rd iteration: 1 3 4 3 4 5 7
                             i   p

After the 4th iteration: 1 3 4 5 4 5 7
                               i   p

After the 5th iteration: 1 3 4 5 7 5 7
                                 i   p

After the 6th iteration: 1 3 4 5 7 5 7
                                   i   p