# How to remove objects from an array most efficiently?

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.

• Firstly, find the first index, then the last, then call the memmove. – kelalaka Aug 6 '19 at 20:26
• So you presume a sorted list, what would you do for an unsorted list? – TVSuchty Aug 6 '19 at 20:32

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 = {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

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