Remove duplicates from sorted array in C++

Remove duplicates from the sorted array in C++.

This same process, due to a sorted array, is to erase the redundant components from the array.

Examples:

Input  : arr[] = {2, 2, 2, 2, 2}
Output : arr[] = {2}
         new size = 1
Input  : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}
Output : arr[] = {1, 2, 3, 4, 5}
         new size = 5

Method 1: (Using extra space)

• Generate an auxiliary temp[] array for storing different aspects.
• Traverse the input array and duplicate different aspects from arr[] to temp[] one by one. Keep records of counting different aspects, as well. Let the count be j.
• Copy j elements to arr[] from temp, and return j.

Example:

// Simple C++ program to remove duplicates
#include<iostream>
using namespace std;
/* Removes duplicate components
The above function will return the prototype model size
Display.*/
int removeDuplicates(int array[], int p)
{
          // Return, if array is empty
          // or contains a single element
          if (p==0 || p==1)
                   return p;
          int temp[p];
          // Start traversing elements
          int k = 0;
          for (int i=0; i<p-1; i++)
                   // If current element is not equal
                   // to next element then store that
                   // current element
                   if (array[i] != array[i+1])
                             temp[k++] = array[i];
          // Store the last element as whether
          // it is unique or repeated, it hasn't
          // stored previously
          temp[k++] = array[p-1];
          // Modify original array
          for (int i=0; i<k; i++)
                   array[i] = temp[i];
          return k;
}
// Driver code
int main()
{
          int array[] = {1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 8, 9, 9 ,10, 11};
          int p = sizeof(array) / sizeof(array[0]);
          // removeDuplicates() returns new size of
          // array.
          p = removeDuplicates(array, p);
          // Print updated array
          for (int i=0; i<p; i++)
          cout << array[i] << " ";
          return 0;
}

Output:

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 2: (Constant extra space)

Just hold a totally separate index for the same array as kept in Method 1 for the different array.

Example:

/* C++ program to remove duplicates in-place*/
#include<iostream>
using namespace std;
int removeDuplicates(int array[], int t)
{
          if (t==0 || t==1)
                   return t;
          // To store index of next unique element
          int k = 0;
          for (int i=0; i < t-1; i++)
                   if (array[i] != array[i+1])
                             array[k++] = array[i];
          array[k++] = array[t-1];
          return k;
}
// Driver code
int main()
{
          int array[] = {1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 9, 9};
          int t = sizeof(array) / sizeof(array[0]);
          // removeDuplicates() returns new size of
          // array.
          t = removeDuplicates(array, t);
          for (int i=0; i<t; i++)
                   cout << array[i] << " ";
          return 0;
}

Output:

Time Complexity: O(n)
Auxiliary Space: O(1)