First, Let us to solve a simpler problem, for input like this

```
Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
```

We want the put all the '0' to the left while the '1' to the right.

```
Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
```

How can you do this in only one pass ?

Here is a possible implementation:

```
void segregate0and1(vector<int> arr)
{
int size=arr.size();
/* Initialize left and right indexes */
int left = 0, right = size-1;
while (left < right)
{
/* Increment left index while we see 0 at left */
while (arr[left] == 0 && left < right)
left++;
/* Decrement right index while we see 1 at right */
while (arr[right] == 1 && left < right)
right--;
/* If left is smaller than right then there is a 1 at left
and a 0 at right. Exchange arr[left] and arr[right]*/
if (left < right)
{
swap(arr[left++], arr[right--]);
}
}
}
```

Now let us solve the 3 color problem, it is just a easy extension based on the above problem.

The most important thing is to make sure you know that to solve the above problem, we use 2 pointers.

Now this problem need 3 pointers.

```
L0 array[0...L0-1] all are 0
L1 array[L0...L1-1] all are 1
unknown array[L1...L2]
L2 array[L2+1...N] all are 2
```

Based on the above definition, it is much more easy to understand the algorithm like this.

```
L0 := 0; L1:= 0; L2 := N-1;
while L1 <= L2 do
Invariant: a[0..L0-1]=0 and a[L0..L1-1]=1 and a[L2+1..N]=2; a[L1..L2] are unknown.
case a[L1] in
0: swap a[L0] and a[L1]; L0++; L1++
1: L1++
2: swap a[L1] and a[L2]; L2--
```

The above index explanation can be viewed in this images.

L1 means mid and L2 means Hi

Based on the above explanation, we get the final AC implementation like this

```
class Solution {
public:
void sortColors(vector<int>& nums) {
int len=nums.size();
if(len<=1) return;
int one=0, two=len-1, zero=0;
while(one<=two){
if(nums[one]==0) swap(nums[one++], nums[zero++]);
else if (nums[one]==2) swap(nums[one], nums[two--]);
else one++;
}
}
};
```

Thanks the posts from G4G

http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

**UPDATE @ 2016/03/04**

How to solve the problem if there are K colors ?

**Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.**

We can use the previous position to store the count of all the K value, use the position K-1 to store the

occurrence of the number K.

To distinguish from the recorded number, we use negative number to store the occurrence.

```
class Solution{
public:
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
void sortColors2(vector<int> &colors, int k) {
for (int i = 0; i < colors.size(); ++i) {
if (colors[i] > 0) {
int pos = colors[i] - 1;
if (colors[pos] <= 0) { // Bucket exists.
--colors[pos];
colors[i] = 0;
}
else { // Init a new bucket.
colors[i] = colors[pos];
colors[pos] = -1;
--i;
}
}
}
for (int i = colors.size() - 1, pos = k - 1; pos >= 0; --pos) {
while (colors[pos] < 0) { // Reorder the color by count of each bucket.
++colors[pos];
colors[i--] = pos + 1;
}
}
}
};
```