C++ program for remove duplicate elements in a sorted array

Removing duplicate elements in a sorted array

Here in this page we will discuss the program for removing duplicate elements in a sorted array in C++ programming language. We will discuss different approaches to solve the given problem. We are given with an array and need to print the array after removing the duplicates.

removing-duplicate-element-in-an-array-cpp

Method Discussed :

  • Method 1 : Using Set Data Structure
  • Method 2 : Without Using Extra Space.

Let’s discuss both methods one by one in brief.

Method 1 :

  • Declare a set data structure.
  • Insert the elements of array in set.
  • Start iterating in set and print the set elements.

Time and Space Complexity :

  • Time Complexity : O(n)
  • Space Complexity : O(n)
Removing dupliacte elements

Method 1 : Code in C++

Run
#include<bits/stdc++.h>

using namespace std;
int main(){
set<int>s;
int arr[] = {10, 10, 20, 30, 30, 30, 40};
int n = sizeof(arr)/sizeof(arr[0]);
for(int i=0; i<n; i++)
s.insert(arr[i]);
for(auto it = s.begin(); it != s.end(); it++)
cout<<*it<<" ";
}

Output :

10 20 30 40

Method 2 :

In this method we will not use extra space.

  • Create a function say duplicate that will return the index value.
  • if(n==0) or (n==1) then return n.
  • Otherwise take a variable say j set j =0;
  • Run a loop from index 0 to n-1
  • If(arr[i]!=arr[i+1]), Then set arr[j++] = arr[i]
  • Finally, return the value of j

Time and Space Complexity :

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

Method 2 : Code in C++

Run
#include<bits/stdc++.h>

using namespace std;

int duplicates(int arr[], int n)
{
    if (n==0 || n==1)
      return n;

    int j = 0;

    for (int i=0; i < n-1; i++)
        if (arr[i] != arr[i+1])
           arr[j++] = arr[i];

    arr[j++] = arr[n-1];

    return j;
}

// Driver code
int main()
{
   int arr[] = {10, 20, 20, 30, 40, 40, 40, 50, 50};
   int n = sizeof(arr) / sizeof(arr[0]);

   n = duplicates(arr, n);

   for (int i=0; i<n; i++)
    cout << arr[i] << " ";

   return 0;
}

Output :

10 20 30 40 50

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

3 comments on “C++ program for remove duplicate elements in a sorted array”


  • SURYA

    The code doesn’t work for array {10, 20, 20, 30, 40, 40, 40, 50, 50,10}, where the duplicate elements are at random index.


    • SURYA

      I Mean Method 2 code:-

      #include

      using namespace std;

      int duplicates(int arr[], int n)
      {
      if (n==0 || n==1)
      return n;

      int j = 0;

      for (int i=0; i < n-1; i++)
      if (arr[i] != arr[i+1])
      arr[j++] = arr[i];

      arr[j++] = arr[n-1];

      return j;
      }

      // Driver code
      int main()
      {
      int arr[] = {10, 20, 20, 30, 40, 40, 40, 50, 50};
      int n = sizeof(arr) / sizeof(arr[0]);

      n = duplicates(arr, n);

      for (int i=0; i<n; i++)
      cout << arr[i] << " ";

      return 0;
      }


  • Sharvari

    Python code:
    size = int(input(“Enter the Array Size : “))
    arr = []
    for i in range(size):
    element = int(input())
    arr.append(element)
    print(arr)
    x = list(dict.fromkeys(arr))
    print(x)