C Program to Delete Duplicate Elements from a Sorted Array

  • Write a C program to delete duplicate elements from a sorted array.
  • Write a C program to print unique elements of an array

Given an sorted integer array of length N. Array elements are sorted in increasing order(inputArray[i] <= inputArray[j] for every i < j). We have to delete duplicate elements from array and print unique elements of the array.

For Example
Sorted array containing duplicate elements : 1 2 2 2 4 4 7 8 9 9
Output array containing only unique elements : 1 2 4 7 8 9

Points to Remember
As the array is sorted, all duplicate elements must exist in adjacent positions.

For Example
In sorted array 1 2 2 2 3 4 4 5 6 7 7 7, all instances of 2, 4, and 7 are in adjacent positions. We will use this fact in below program to delete duplicate elements.
Algorithm to delete duplicate elements from a sorted array
Let inputArray be an array of length N, and readIndex and writeIndex are two integer variables to store index references.

  • In a sorted array, all duplicate elements must exist in adjacent positions.
  • At any instant, all element to the left of writeIndex are unique.
  • inputArray[writeIndex] is always the last unique element added.
  • We will traverse inputArray using using readIndex. If inputArray[readIndex] is not equal to inputArray[writeIndex], then inputArray[readIndex] is not same as the last unique element added. Hence, add inputArray[readIndex] in set of unique elements.
  • At the end of traversal, we will get all unique elements between index 0 to writeIndex.

C program to delete duplicate elements from a sorted array

C Program to Delete Duplicate Elements from a Sorted Array

/*
* C Program to delete duplicate elements from an sorted array
*/
#include <stdio.h>
#include <conio.h>
 
int main(){
    int inputArray[500], elementCount, counter;
    int readIndex, writeIndex;
     
    printf("Enter number of elements in array: ");
    scanf("%d", &elementCount);
         
    printf("Enter %d numbers in increasing order \n", elementCount);
    for(counter = 0; counter < elementCount; counter++){
        scanf("%d", &inputArray[counter]);
    }
    /* Input Validation
     * Input Elements must be in increasing order
     */
    for(counter = 1; counter < elementCount; counter++){
        if(inputArray[counter] < inputArray[counter -1]){
            printf("Invalid Input: elements not in increasing order \n");
            return 1;
        }
    }
    /*
     * All the elemets before writeIndex are unique.
     * readIndex scan elements from left to write and 
     * tries to find a duplicate element. 
     */
    for(readIndex=1, writeIndex=0; readIndex < elementCount; readIndex++){
        if(inputArray[readIndex] != inputArray[writeIndex]){
            writeIndex++;
            inputArray[writeIndex] = inputArray[readIndex];
        }
    }
     
    /* Print unique element */
    printf("Unique Elements\n");
    for(counter = 0; counter < writeIndex + 1; counter++){
        printf("%d ", inputArray[counter]);
    } 
         
    getch();
    return 0;
}

Program Output

Enter number of elements in array: 8
Enter 8 numbers in increasing order 
0 0 1 2 2 2 3 7
Unique Elements
0 1 2 3 7