C++ Program to Remove duplicates from Sorted Array

You will learn to solve the problem of how to write a C++ program to remove duplicates from a sorted array. So the important point is that the array is already sorted in either ascending or descending order.

Now let’s see the problem statement,

Problem Statement: Given an integer array “arr“, sorted in increasing order, remove the duplicates in place such that each unique element appears only once. The relative order of the elements should be kept the same.

If there are N elements after removing the duplicates, the first N elements of the array are important. The remaining elements of arr are not important as well as the size of arr. That means your created function returns the number of unique elements in arr.

Let’s see some examples to understand the problem.

Example 1:

Input: {1,1,2}

Output: = [1,2,_]

Explanation: Your function should return s = 2, because arr has total 2 unique elements.
We don't care the elements after the s (hence they are underscores).




Example 2:

Input: {-1,-1, 0,0,1,2,2,3,3,4}

Output: 6, arr = {-1,0,1,2,3,4,_,_,_,_,_}

Explanation: Your function should return s = 6, because arr has total 6 unique elements.
We don't care the elements after the s (hence they are underscores).

Solution 1: Brute Force

This is the simplest solution to remove duplicate elements in a given array. Here I will use the Hash set to solve this problem. As we know sets are a type of associative container in which each element has to be unique because the value of the element identifies it. So it would be helpful for us to solve this problem.

Approach:

Create a HashSet.
Execute a for loop throughout the array.
Put each element of the array in the set.
Store the size of the set in a variable s.
Now put elements of the set in the original array.

C++ Program to Remove Duplicates from Sorted Array:

#include<bits/stdc++.h>

using namespace std;
int removeDuplicates(int arr[], int sz)
{
    set <int> set;
    for (int i = 0; i < sz; i++)
    {
        set.insert(arr[i]);
    }
    //Size of unique elements
    const int s = set.size();
    int index = 0;
    for (int value: set)
    {
        arr[index++] = value;
    }
    return s;
}


int main()
{
    int arr[] = {-1,-1,0,1,1,2,2,2,3,3};
    const int sizeOFArray = sizeof(arr)/sizeof(arr[0]);
    //remove duplicate elements
    const int s = removeDuplicates(arr, sizeOFArray);
    cout << "The array after removing duplicate elements is " << endl;

    //print array elements
    for (int i = 0; i < s; i++)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

The array after removing duplicate elements is
-1 0 1 2 3

Two pointers Approach without taking extra space:

In a sorted array all duplicate elements are always adjacent. So you just need to compare the input array elements with their adjacent ones. If they are equal that means the duplicate element is present in the input array. In that situation, you just need to avoid duplicate elements and only copy the elements in the intermediate array which is not matched with their adjacent elements.

Approach:

Create a variables i and initialize the i as 0;
Traverse input array from the index 1 (j=1) to the length of the array.
Now in the for loop check If arr[j] != arr[i], increase ‘i’ and copy arr[j] to arr[i] (arr[i] = arr[j]).
In the last return (i+1), i.e. size of the array of unique elements.

#include<bits/stdc++.h>
using namespace std;

int removeDuplicates(int arr[], int array_size)
{
    int i = 0;
    for (int j=1; j<array_size; ++j)
    {
        // If current element is not equal
        // to adjacent element then store that
        // current element in temp array
        if (arr[i] != arr[j])
        {
            arr[++i] = arr[j];
        }
    }
    //unique element array len
    return (i+1);
}


int main()
{
    int arr[] = {0, 1, 1, 1, 2, 2, 6, 6, 9};

    //get array size
    const int arr_size = sizeof(arr)/sizeof(arr[0]);

    //remove duplicate elements
    const int uniqueArrayLen = removeDuplicates(arr, arr_size);

    cout << "Unique array len = " << uniqueArrayLen << endl;
    cout << "Array after removing duplicate elements is " << endl;

    for (int i = 0; i < uniqueArrayLen; ++i)
    {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

Unique array len = 5

Array after removing duplicate elements is: 0 1 2 6 9

Recommended Articles for you: