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.

• kelalaka: Firstly, find the first index, then the last, then call the memmove.
• TVSuchty: So you presume a sorted list, what would you do for an unsorted list?

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

• Gilles 'SO- stop being evil': I think the loop would be easier to understand if you iterated over p rather than i.
• TVSuchty: Hey, what a smart algorithm! Did you come up with this on your own?
• xskxzr: @TVSuchty Yes, but I think this algorithm is not hard and can be found in the Internet easily.
• TVSuchty: For a (soon) first grader this is kinda mindblowing! I think this pointer concept can be used in various situations.