can someone please post the onepass solution that uses constant space .
I have been able to do it in two pass only.
Anyone with one pass and constant space solution ?

Hi @xianlei, since your answer has been selected as best answer, I won't hide your post. But discuss do not allow only code post, could you please add words about your algorithm and make key comments in your code? Thanks.

Hi @its_dark, could you please update your post with your two pass code solution and detail how it works? It would make people know more about your question, and will bring them different view of this problem. Thanks.

Maintain the starting index of 0s, 1s, and 2s at anytime. (actually, 0s will always start from index 0)
If next value is 0, right shift 1s and 2s, and put the 0 at proper location.
For shifting, we don't have to really shift the array, only 3 positions need to be changed.
Similar for 1 or 2

Really smart solution!
I can describe it in this way:
 p is the input iterator, reads new values, is as faster than others so no problems of
reading values already overwritten.  i counts the number of 0 found, and a the same time writes zeroes.
 j counts the number of 0 + 1 found, and at the same time writes 1.
 k counts the number of 0 + 1 + 2 found and at the same time writes 2.
Your solution can be improved in this way:
{
public void sortColors(int[] A) {int i=1, j=1; for(int p = 0; p < A.length; p++) { int v = A[p]; A[p] = 2; if (v == 0) { A[++j] = 1; A[++i] = 0; } else if (v == 1) { A[++j] = 1; } } }
}
 p is the input iterator, reads new values, is as faster than others so no problems of

While xianlei and riccardo's answers are really smart and neat, the running of their codes involves continuous overwriting that compromises the performance. My code is not that beautiful, but it is onepass with constant space and runs faster. (124 ms vs 180 ms (riccardo's version) by python codes)
class Solution: # @param A a list of integers # @return nothing, sort in place def sortColors(self, A): red, blue = 0, len(A)1 i = 0 while i <= blue: if A[i] == 0: if i > red: A[red] = 0 A[i] = 1 red += 1 elif A[i] == 2: while blue > i and A[blue] == 2: blue = 1 if blue == i: break if A[blue] == 0: A[red] = 0 if i > red: A[i] = 1 red += 1 else: A[i] = 1 A[blue] = 2 blue = 1 i += 1

public class Solution { public void sortColors(int[] A) { int i = 0; int indexes[] = {0, 0, 0}; while(i < A.length) { int num = A[i]; //Correct position if(i == indexes[num]) { i++; } else { //Exchange A[i] = A[indexes[num]]; A[indexes[num]] = num; } //Increments the index indexes[num]++; //Align higher indexes for(int o=num+1; o<indexes.length; o++) { if(indexes[o]<indexes[o1]) indexes[o] = indexes[o1]; } } } }

void sortColors(int A[], int n) { if (n<2) return; int numof0 = 0; int numof2 = 0; int i; while ((numof0 < n) && (A[numof0]== 0)) numof0++; i = numof0; while ((i<n) && (i<(nnumof2))) { if ((A[i] ==0) && (numof0 != i)) { memmove((void *)&A[1], (void *)A, (i)*sizeof(int)); A[0] = 0; numof0++; } if ((A[i] ==2) && (numof2 < (ni1)) ){ memmove((void *)&A[i], (void *)&A[i+1], (ni1)*sizeof(int)); A[n1] = 2; numof2++; i; } i++; } };
Here is another way for doing it. When you see a '0', insert at the beginning of the array. If you see an '1', leave it. If you see a '2', insert it at the end. Just be careful to "step back" when you insert '2' at the end

I scan the whole array one element by one element and swap those elements when some conditions are match. Here is my code. I found it more readable. Comments are welcome!
class Solution { public: void sortColors(int A[], int n) { int left = 0; int right = n  1; int current = 0; while (current <= right) { if (A[current] == 0) { swap(A[current], A[left++]); } else if (A[current] == 1) { current++; } else { swap(A[current], A[right]); } current = max(current, left); } return; } };

Hello, this is my O(n) solution,constant space. the idea is similar to partition technique in quick sort.
index p1 to denote the last position of 0
p2 to denote last position of 1(if there is).public void sortColors(int[] A) { int n=A.length; int p1=1; int p2=1; for(int i=0;i<n;i++){ if(A[i]==0){ p1++; swap(A,p1,i); if(p2!=1){ p2++; swap(A,p2,i); } } else if(A[i]==1){ if(p2==1) p2=p1; p2++; swap(A,p2,i); } } } public void swap(int[] A,int i,int j){ int temp=0; temp=A[i]; A[i]=A[j]; A[j]=temp; }

void sortColors(int A[], int n) { int mark_0 = 0; int mark_1 = 0; int mark_2 = 0; for(int i=0;i<n;i++){ if(A[i]==0){ A[mark_0] = 0; if(mark_1!=mark_0) A[mark_1] = 1; if(mark_2!=mark_1) A[mark_2] = 2; mark_0++; mark_1++; mark_2++; } else if(A[i]==1){ A[mark_1] = 1; if(mark_2!=mark_1) A[mark_2] = 2; mark_1++; mark_2++; } else if(A[i]==2){ A[mark_2] = 2; mark_2++; } } }