Remove duplicates from sorted array (most efficient way)

Since it is a sorted array any duplicates would be next to each other. So start at the beginning and compare each element to it neighbor on its right. If there are no duplicates then you have made n-1 comparisons.

If you find a duplicate you are going to have a hole. Since it is an array an not a link list you will need to move every element down. (You could create a new array if that was allowed.) However you do not just want to start shifting, you can simply mark with a pointer or counter where the hole is and move on to the next comparison. When you get the next non-duplicate you move(copy) that element into the hole and increment your hole counter by 1.

So here is some C code that will do just that.

bool RemoveDuplicates(int array[], int iSize){

//validation: if array is empty, null, just one element
if(iSize < 1) return false;
if(array == NULL) return false;
if(iSize == 1) return true;

int left_compare = 0;
int right_compare = 1;
bool start_move = false;
int hole = iSize;

for( ; right_comp
if(array[left_comp] == array[right_comp]){

if(!start_move){
start_move = true;
hole = right_comp;
}
}
else if(start_move){
array[hole++] = array[right_comp];
}
}


//fill up the rest of the elements with zeros as they are no longer needed. this is //needed
//in the case where the right_comp comes to the end and there are still holes in //the array
for(;hole array[hole] = 0;
}

return true;
}

void main(){
int array[] = {1,1,1,1,1,1,1,1,2,2,4,5,7,8,8,9,9,10,11,11,12,13,14};
int iSize = sizeof(array)
int i;


if(!bRemoveDuplicates(array,iSize))
{
cout< }


cin>>i;

}