Remove Duplicate from Sorted array (C++)

Question : You are given an array which is sorted , Your task is to remove the duplicate elements and return the size of the new array .

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

Brute Solution :

You can take a hashset data structure to solve this problem . Now start iterating your given array and insert each element to the hashset. Now by property , hashset only contains unique element . So once you iterate the array and try inserting the elements to the hashset , after your complete iteration hashset will contain only unique elements from the given array , so now the size of hashset is your answer .
Pseudo code :
for(i=0 to n-1){
return s.size() ;

Time complexity : O(n)
Space complexity : O(1)

Optimal Solution :

To optimize the above solution we can go with two pointer approach . We can take two pointer as i and j .

Two get a understanding of the approach lets take an example array as :
We initially keep pointer i at 0th index and we have one more pointer j so our j pointer is at 1st index so we see that i and j are having same values so they’re not different so we need element which is different than i so j pointer to a place ahead .Now j is at 2nd index , i.e. arr[2]=2 so at this point we can see the value at the index i and the valueat index j are different.Now move the i pointer to one step , i.e i is at 1st place , arr[i]=1 now , after that take the 2 i.e arr[j]=2 and place it in arr[i] which is 1 now . so basically ; do arr[i]=arr[j] .

Our next task is to find out an element which is not 2 so again we move j .So we will keep moving j till we find 3. once we find 3 , we repeat the above steps . i.e. i++ and arr[i]=ar[j] .
We follow these steps , till we complete the array iteration . Once J complete the iteration of array , now till i , we have all the unique elements , so we can simply return i+1.

Code :
C++ :
Function to Find the Size of Array with Unique Elements :

int removeDuplicates(vector<int>& nums) {

int n=nums.size();

if(n==1 or n==0) return n;

    int j=1;
    int i=0;




    return i+1;

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

Partner Sites

Be the first to comment

Leave a Reply

Your email address will not be published.