O(n) solution is good enough


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


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


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.


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])
        z = 1;
    while(j<n && A[i]==A[j])
    for(int k=j;k<n;k++)
        A[k-j+i+z+1] = A[k];
    n = n-j+i+z+1;
return n;