Very simple and easy to understand solution O(n);


#1

void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
void Solution::sortColors(vector &A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details

int mark=0;
for(int i=0;i<A.size();i++){
    if(A[i]==0){
        swap(A[i],A[mark]);
        mark++;
    }
}

for(int i=mark;i<A.size();i++){
    if(A[i]==1){
        swap(A[i],A[mark]);
        mark++;
    }
}

}