[Sort][Two Pointers] Sort Color

1. Example
n obejcts colored red(0), white(1), or blue(2)
sort them so that the objects of the same color are adjacent.

s=[0,1,2,0,1,2,0,0,1,1,2,2]
sorted s = [0,0,0,0,1,1,1,1,2,2,2,2]

Follw Up: n Colors?
2. Implementation
Q1: merge sort, quick sort ?
A1: it takes O(n log(n))
Q1: only 3 elements, using counting sort = > O(n)
A1: count[0] = .. ,count[1] = .., count[2] =..
Q1: how to do it in-place?
A1: replace existing elements
Q1: [0,1,2,0,1,2,0,0,1,1,2,2]
[0] = 4
[1] =4
[2] =4
0, 0,0,0, 1,1,1,1,2,2,2,2
    2 1 0  3 2 1 0 3 2 1 0
// NOTE:
// consumes 0 first and then 1 and then..n

// NOTE:
// KEEP the last colored element and change the other two kind
if (nums[i] == 0) { 

nums[i] =2; 

nums[idx1++] = 1; // the reason idx1++ is because when insert 0 at idx0, idx1 would be push next. idx1 = idx0 + # of 1 

nums[idx0++] = 0; // overwrite 1 

} 

else if ( nums[i] == 1) { 

nums[i]=2; 

nums[idx1++] =1;

 }

// Time:O(n), SpacE:O(k) array with size of k
public void sortColors(int[] nums)
{




      // validate the input
      if ( nums == null || nums.length == 0)
        return;
 
 


      int[] count = new int[3];
      for (int i = 0 ; i < nums.length; i++)
      {
            count[nums[i]]++;
      }





      for (int i = 0 ; i < nums.length;i++)
      {
            if (nums[i] == 2)
            {
                  if ( count[0] != 0)
                  {
                      nums[i] = 0;
                      count[0]--;
                  } 
                  else if ( count[1] != 0)
                  {
                      nums[i] =1;
                      count[1]--;
                  }
                  else if (count[2] != 0)
                      count[2]--;
            } 
            else if ( nums[i] == 1)
            {
                  if (  count[0] != 0 )
                  {
                      nums[i] = 0;
                      count[0]--;
                  }
                  else if ( count[1] != 0)
                  {
                      count[1]--;
                  }
                  else if ( count[2] != 0)
                  {
                      nums[i] =2;
                      count[2]--;
                  }
            }
            else 
            {
                  if (count[0] != 0)
                     count[0]--;
                  else if (count[1] != 0)
                  {
                     nums[i] = 1;
                     count[1]--;
                  }
                  else if ( count[2] != 0)
                  {
                     nums[i] = 2;
                     count[2]--;
                  }
            }
      
      }




}
[0,1,2,0,1,2,0,0,1,1,2,2]

                 2 2 2
 3 2 1 0 3 2 1 0 3 2 

// Time :O(n), Sapce:O(k)
if (nums== null || nums.length == 0)
    return;



int idx0 = 0; // array index for element 0
int idx1 = 0; // array index for element 1




for ( int i = 0 ; i < nums.legnth;i++)
{
     
     // KEEP the last colored element and change the other two kind
     // move 0 forward according to current array index for Zero
     if (nums[i] == 0)
     {
          nums[i] =2;
          nums[idx1++] = 1; // the reason idx1++ is because when insert 0 at idx0, idx1 would be push next. idx1 = idx0 + # of 1
          nums[idx0++] = 0; // overwrite 1
     }
     else if ( nums[i] == 1)
     {
          nums[i]=2;
          nums[idx1++] =1;
     }

}

3. Similar Ones
(M) Sort List (Divide and Conquer) (Merge Sort)