This is my constant space solution. It basically tracks the last 0 and first 2 in the partially sorted array. During the pass, for example, we are on the fifth element.

0 0 0 1 ? x x x x 2 2

If it's 0, we will swap it with the first nonzero element; if it's 1, keep it that way; if it's 2, they swap with the third last element.

Let me know if there is more room for improvement!

```
class Solution {
public:
void swap(int A[], int i, int j)
{
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
void sortColors(int A[], int n)
{
int ind0(0), ind2(n-1);
int i=0;
while (i<n)
{
if (A[i]==0)
{
if (i==0 || A[i-1]==0)
{
++i;
ind0 = i;
}
else if (A[i-1]!=0)
{
swap(A,i,ind0);
ind0++;
}
}
else if (A[i]==1)
{
++i;
}
else if (A[i]==2)
{
if (i < ind2)
{
if (A[ind2] != 2)
swap(A,i,ind2);
--ind2;
}
else
{
++i;
}
}
}
}
};
```