Write code to remove duplicates in a sorted array.

There are a number of ways to remove duplicates from a sorted array. Here are a few C programs...


Method1

In this simple C program, we change the original array and also send the new size of the array back to the caller.


#include < stdio.h >

int removeDuplicates(int a[], int array_size);

// The main function
int main()
{

// Different test cases..
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;


my_array1_size = removeDuplicates(my_array1, my_array1_size);
my_array2_size = removeDuplicates(my_array2, my_array2_size);
my_array3_size = removeDuplicates(my_array3, my_array3_size);
my_array4_size = removeDuplicates(my_array4, my_array4_size);
my_array5_size = removeDuplicates(my_array5, my_array5_size);
my_array6_size = removeDuplicates(my_array6, my_array6_size);
my_array7_size = removeDuplicates(my_array7, my_array7_size);

return(0);
}


// Function to remove the duplicates
int removeDuplicates(int a[], int array_size)
{
int i, j;

j = 0;


// Print old array...
printf("\n\nOLD : ");
for(i = 0; i < array_size; i++)
{
printf("[%d] ", a[i]);
}


// Remove the duplicates ...
for (i = 1; i < array_size; i++)
{
if (a[i] != a[j])
{
j++;
a[j] = a[i]; // Move it to the front
}
}

// The new array size..
array_size = (j + 1);


// Print new array...
printf("\n\nNEW : ");
for(i = 0; i < array_size; i++)
{
printf("[%d] ", a[i]);
}
printf("\n\n");



// Return the new size...
return(j + 1);
}




And here is the output...


OLD : [1] [1] [2] [3] [5] [6] [6] [7] [10] [25] [100] [123] [123]
NEW : [1] [2] [3] [5] [6] [7] [10] [25] [100] [123]


OLD : [1] [2] [3] [5] [6]
NEW : [1] [2] [3] [5] [6]


OLD : [1] [1] [1] [1] [1]
NEW : [1]


OLD : [123] [123]
NEW : [123]


OLD : [1] [123] [123]
NEW : [1] [123]


OLD : [123] [123] [166]
NEW : [123] [166]


OLD : [1] [2] [8] [8] [24] [60] [60] [60] [60] [75] [100] [100] [123]
NEW : [1] [2] [8] [24] [60] [75] [100] [123]





Method2

If we dont want to change the input array and just want to print the array without any duplicates, the solution is very simple. Check out the removeDuplicatesNoModify() function in the program below. It keeps a track of the most recently seen number and does not print any duplicates of it when traversing the sorted array.



#include < stdio.h >

void removeDuplicatesNoModify(int my_array[], int my_array1_size);
void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end);


// The main function
int main()
{
// Different inputs...
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;


removeDuplicatesNoModify(my_array1, my_array1_size);
removeDuplicatesNoModify(my_array2, my_array2_size);
removeDuplicatesNoModify(my_array3, my_array3_size);
removeDuplicatesNoModify(my_array4, my_array4_size);
removeDuplicatesNoModify(my_array5, my_array5_size);
removeDuplicatesNoModify(my_array6, my_array6_size);
removeDuplicatesNoModify(my_array7, my_array7_size);

return(0);
}



// This function just prints the array without duplicates.
// It does not modify the original array!

void removeDuplicatesNoModify(int array[], int array_size)
{
int i, last_seen_unique;

if(array_size <= 1){return;}

last_seen_unique = array[0];

printf("\n\nOld : ", array_size);

for(i = 0; i < array_size; i++)
{
printf("[%2d] ", array[i]);
}

printf("\nNew : ", array_size);

printf("[%2d] ", array[0]);
for(i=1; i < array_size; i++)
{
if(array[i]!=last_seen_unique)
{
printf("[%2d] ", array[i]);
last_seen_unique = array[i];
}
}

printf("\n");
}




And here is the output..

Old : [ 1] [ 1] [ 2] [ 3] [ 5] [ 6] [ 6] [ 7] [10] [25] [100] [123] [123]
New : [ 1] [ 2] [ 3] [ 5] [ 6] [ 7] [10] [25] [100] [123]


Old : [ 1] [ 2] [ 3] [ 5] [ 6]
New : [ 1] [ 2] [ 3] [ 5] [ 6]


Old : [ 1] [ 1] [ 1] [ 1] [ 1]
New : [ 1]


Old : [123] [123]
New : [123]


Old : [ 1] [123] [123]
New : [ 1] [123]


Old : [123] [123] [166]
New : [123] [166]


Old : [ 1] [ 2] [ 8] [ 8] [24] [60] [60] [60] [60] [75] [100] [100] [123]
New : [ 1] [ 2] [ 8] [24] [60] [75] [100] [123]





Method3

Here is a slightly compilcated, but more visual version of the removeDuplicates() function. It shrinks the original array as and when it find duplicates. It is also optimized to identify continuous strings of duplicates and eliminate them at one shot.




#include < stdio.h >

void removeDuplicates(int array[], int *array_size) ;
void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end);


// The main function
int main()
{
// Different inputs...
int my_array1[] = {1, 1, 2, 3, 5, 6, 6, 7, 10, 25, 100, 123, 123};
int my_array1_size = 13;

int my_array2[] = {1, 2, 3, 5, 6};
int my_array2_size = 5;

int my_array3[] = {1, 1, 1, 1, 1};
int my_array3_size = 5;

int my_array4[] = {123, 123};
int my_array4_size = 2;

int my_array5[] = {1, 123, 123};
int my_array5_size = 3;

int my_array6[] = {123, 123, 166};
int my_array6_size = 3;

int my_array7[] = {1, 2, 8, 8 , 24, 60, 60, 60, 60, 75, 100, 100, 123};
int my_array7_size = 13;

removeDuplicates(my_array1, &my_array1_size);
removeDuplicates(my_array2, &my_array2_size);
removeDuplicates(my_array3, &my_array3_size);
removeDuplicates(my_array4, &my_array4_size);
removeDuplicates(my_array5, &my_array5_size);
removeDuplicates(my_array6, &my_array6_size);
removeDuplicates(my_array7, &my_array7_size);

return(0);
}




// Changes the original array and resets the size of the array if duplicates
// have been removed.

void removeDuplicates(int array[], int *array_size)
{
int i, j, k, l;
int current_pos;
int dup_start;
int dup_end;

printf("\nInitial array (size : [%d])\n\n", *array_size);
for(i = 0; i < *array_size; i++)
{
printf("[%2d] ", array[i]);
}
printf("\n\n\n------------------------------------------------\n");


if(*array_size == 1){return;}


// Remove the dups...
for (i = 0; (i < *array_size); i++)
{
//Start with the next element in the array and check if its a duplicate...
for(j = i+1; (j < *array_size); j++)
{
if(array[i]!=array[j])
{
// No duplicate, just continue...
break;
}
else
{
// The next element is a duplicate.
// See if there are more duplicates, as we want to optimize here.
//
// That is, if we have something like
//
// Array : [1, 1, 1, 2]
//
// then, we want to copy 2 directly in the second position and reduce the
// array to
//
// Array : [1, 2].
//
// in a single iteration.

current_pos = i;
dup_start = j;

j++;

while((array[i]==array[j]) && (j < *array_size))
{
j++;
}

dup_end = j-1;

print_array(array, *array_size, current_pos, dup_start, dup_end);

// Now remove elements of the array from "dup_start" to "dup_end"
// and shrink the size of the array.

for(k = (dup_end + 1), l = dup_start ; k < *array_size;)
{
array[l++]=array[k++];
}

// Reduce the array size by the number of elements removed.
*array_size = *array_size - (dup_end - dup_start + 1);

}
}
}

printf("\n\n------------------------------------------------");
printf("\n\nFinal array (size : [%d])\n\n", *array_size);
for(i = 0; i < *array_size; i++)
{
printf("[%2d] ", array[i]);
}
printf("\n\n");

}




// This function prints the array with some special pointers to the numbers that
// are duplicated.
//
// Dont bother too much about this function, it just helps in understanding
// how and where the duplicates are being removed from.

void print_array(int array[], int array_size, int current_pos, int dup_start, int dup_end)
{
int i;

printf("\n\n");

for(i = 0; i < array_size; i++)
{
printf("[%2d] ", array[i]);
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if((i == current_pos) ||
(i == dup_start && i == dup_end) ||
((i == dup_start || i == dup_end) && (dup_start != dup_end)))
{
printf(" ^ ");
}
else
{
printf(" ");
}
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if((i == current_pos) ||
(i == dup_start && i == dup_end) ||
((i == dup_start || i == dup_end) && (dup_start != dup_end)))
{
printf(" | ");
}
else
{
printf(" ");
}
}

printf("\n");

for(i = 0; i < array_size; i++)
{
if(i == current_pos)
{
printf(" C ");
}
else if(i == dup_start && i == dup_end)
{
printf(" S/E ");
}
else if((i == dup_start || i == dup_end) && (dup_start != dup_end))
{
if(i == dup_start)
{
printf(" S--");
}
else
{
printf("--E ");
}
}
else if(i > dup_start && i < dup_end)
{
printf("-----");
}
else
{
printf(" ");
}
}

}





And here is the output (for one of the inputs)...


C - Current position.
S - Start of duplicates.
E - End of duplicates.




Old : [ 1] [ 2] [ 8] [ 8] [24] [60] [60] [60] [60] [75] [100] [100] [123]

-------------------------------------------------------------------------
[ 1] [ 2] [ 8 (C) ] [ 8 (S/E) ] [24] [60] [60] [60] [60] [75] [100] [100] [123]


[ 1] [ 2] [ 8] [24] [60 (C)] [60 (S)] [60 (E)] [60] [75] [100] [100] [123]


[ 1] [ 2] [ 8] [24] [60] [75] [100 (C)] [100 (S/E)] [123]

-------------------------------------------------------------------------
New : [ 1] [ 2] [ 8] [24] [60] [75] [100] [123]



If there are other elegant methods of removing duplicate numbers from an array, please let me know!.