O(n) solution is good enough


#1

Don’t delete the numbers one by one. Try to delete bunch of them together.


#2

deleting them one by one is O(n^2)


#3

And so is deleting them in bunch. The complexity of doing so is O(n*m), where m is the number of distinct elements, which in worst case is (n/3), considering every element is there 3 times. It’s just 3 times better than one by one.


#4

My Solution :

int Solution::removeDuplicates(vector<int> &A) {
int n = A.size();
if(n==0 || n==1)
    return n;
for(int i=0;i<n;i++)
{
    int j = i+1;
    int z = 0;
    if(j<n && A[i]==A[j])
    {
        j++;
        z = 1;
    }
    while(j<n && A[i]==A[j])
        j++;
    for(int k=j;k<n;k++)
        A[k-j+i+z+1] = A[k];
    n = n-j+i+z+1;
    if(z==1)
        i++;
}
return n;

}