C program to remove duplicates from sorted array

In this blog post, we learn how to write a C program to remove duplicates from sorted array? So here we will write a C program to remove duplicates from sorted array. Suppose ‘arr’ is a sorted integer array of size N and task to remove the duplicates elements from the array in such way that each element appears only once.

Example,

Input array: int arr[] = {1, 1, 1, 3, 5, 5, 7};

Output array:  {1, 3, 5, 7};

Note: Because the input array is sorted so duplicates are always adjacent.

Solution 1: Brute Force

It is the simplest solution to remove duplicate elements in a given array. In which you need to create an intermediate temporary array of size N (size of input array).

As we know that in a sorted array all duplicates are always adjacent. So now need to compare the input array elements with their adjacent. If they are equal that means the duplicate element is present in the input array. So to avoid duplicate elements we only copy the elements in the intermediate array which is not matched with their adjacent elements.

After traversing the whole array we will copy all the elements of the intermediate array back to the original array and return the original array.

#include 

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


int removeDuplicates(int arr[], int array_size)
{
    //intermediate temp array
    int temp[array_size];
    unsigned int uniqueArrayLen = 0;

    //if array is empty
    // or contains a single element
    if (array_size <= 1)
    {
        uniqueArrayLen = array_size;
    }
    else
    {
        unsigned int i =0;

        for (i=0; i<array_size-1; i++)
        {
            // If current element is not equal
            // to adjacent element then store that
            // current element in temp array
            if (arr[i] != arr[i+1])
            {
                temp[uniqueArrayLen++] = arr[i];
            }
        }

        // Store the last element as whether
        // it is unique or repeated, it hasn't
        // stored previously
        temp[uniqueArrayLen++] = arr[array_size-1];

        //Now copy temp array in original array
        for (i=0; i<uniqueArrayLen; i++)
        {
            arr[i] = temp[i];
        }
    }

    return uniqueArrayLen;
}



int main()
{
    int arr[] = {1, 1, 1, 3, 5, 5, 7};

    int i = 0;

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    unsigned int uniqueArrayLen = removeDuplicates(arr, arr_size);

    //print unique array
    for (i=0; i<uniqueArrayLen; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

Output:

output array contains {1, 3, 5, 7};

If you want to learn more about the C language, you can check this course, Free Trial Available.

You can see in the above method we are using an extra temporary array. If you want, you can save the extra space by maintaining separate index. The logic will be same as discuss in the above method. Let’s see the codeĀ 

#include <stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])


int removeDuplicates(int arr[], int array_size)
{
    unsigned int uniqueArrayLen = 0;

    //if array is empty
    // or contains a single element
    if (array_size <= 1)
    {
        uniqueArrayLen = array_size;
    }
    else
    {
        unsigned int i =0;

        for (i=0; i<array_size-1; i++)
        {
            // If current element is not equal
            // to adjacent element then store that
            // current element in temp array
            if (arr[i] != arr[i+1])
            {
                arr[uniqueArrayLen++] = arr[i];
            }
        }

        // Store the last element as whether
        // it is unique or repeated, it hasn't
        // stored previously
        arr[uniqueArrayLen++] = arr[array_size-1];


    }

    return uniqueArrayLen;
}




int main()
{
    int arr[] = {1, 1, 1, 3, 5, 5, 7};

    int i = 0;

    //get array size
    int arr_size = ARRAY_SIZE(arr);

    unsigned int uniqueArrayLen = removeDuplicates(arr, arr_size);

    //print unique array
    for (i=0; i<uniqueArrayLen; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

Output:

output array contains {1, 3, 5, 7};