# 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 :
set<int>s;
for(i=0 to n-1){
s.insert(arr[i])
}
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 :
arr=[1,1,2,2,2,3,3]
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 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;

for(j=1;j<n;)
{

if(nums[i]==nums[j])
{
j++;
}
else
{
nums[i+1]=nums[j];
i++;
j++;
}

}

return i+1;
}``````

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