O(n) Solution 2 pointers 2 passes


#1

void Solution::sortColors(vector &A) {
int l = 0, r = A.size()-1;

while(l<r)
{
    while(A[l]==0) l++;
    while(A[r]==2) r--;
    
    if(A[l]==2 && l<r) swap(A[l],A[r]);
    l++;
}

l = 0, r = A.size()-1;
while(l<r)
{
    while(A[l]==0) l++;
    while(A[r]==2) r--;
    
    if(A[r]==0 && l<r) swap(A[l],A[r]);
    r--;
}

}