TLE at submission ! please someone point out the mistake


#1

int Solution::removeDuplicates(vector &A) {

int n=A.size();
if (n==0 || n==1)
    return n;
int count=n;
vector<int>::iterator it1=A.begin();
it1++;
vector<int>::iterator it2=A.begin();
while(it1!=A.end()){
    if (*it2==*it1){
        count--;
        A.erase(it1);
       // it1++;
    }
    else{
        it1++;
        it2++;
    }
}
return count;

}


#2

Every time you use A.erase() it takes o(n) time complexity, so overall will be o(n^2),instead use another vector (v) and store in it, later clear all values in A and point it to v


#3

Use two pointers and whenever you find mismatch then swap the data for your resultant array rather than deleting it and then return the length of your selected array

int n=A.size();if(n==1)return 1;
int st=0;
int end=st+1;
int pos=1;
while(end<A.size())
{
if(A[end]==A[st])
end++;
else
{
st=end;
A[pos++]=A[st];
end=st+1;
}
}
return pos;


#4

Deleting the element from last worked for me.

while(i<a.size())a.remove(a.size()-1);


#5

Actually If you try to do using erase function it will leads to increase the time complexity and make it into
n^2 in worst case…

Now You have 2 options

  1. Create auxillary array and store into it and return…
  2. Without auxillary array…

If you try to do using 1st method, It is okay but not accepted in Interviews So I would recommended you to select the method 2

For understanding method 2 see my Solution from given link

My solution Link