75. Sort Colors Leetcode Java

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

Solution:

As the follow up mentioned, count sort is a very intuitive solution.

Counting the number of 0s 1s and 2s and then assign the value to the array according to the counts.

Standard counting sort solution:

 public void sortColors(int[] A) {  
    if(A==null || A.length<=1) return;  
    int k=3;  
    int[] B=new int[A.length];  
    int[] helper= new int[k];  
    for(int i=0; i< A.length;i++){  
      helper[A[i]]++;  
    }  
    for(int i=1;i<k;i++) helper[i]+=helper[i-1];  
    for(int i=0; i<A.length;i++){  
      B[helper[A[i]]-1]=A[i];  
      helper[A[i]]--;  
    }  
    for(int i=0;i<A.length;i++){  
      A[i]=B[i];  
    }  
    return;  
   }  

Two pointer solution:
Using two pointer to keep track the next position for 0 and 1. 
If the current element is 0, put to the next position of 0 , and aslo assign 1 to the next position of 1, and assign current value as 2.
If the current element is 1, assign 1 to the next position of 1 and assign current value to 2. 
Do nothing if current element is 2.
Tips: Assign the value from back to front(from bigger to smaller), which can avoid processing the case when there are no 0 or 1 presented in the array.

 public void sortColors(int[] A) {  
    if(A==null || A.length<=1) return;  
    int zind=0;  
    int oind=0;  
    for(int i=0;i<A.length;i++){  
      if(A[i]==0){  
        A[i]=2;  
        A[oind++]=1;  
        A[zind++]=0;  
      }  
      else if(A[i]==1){  
        A[i]=2;  
        A[oind++]=1;  
      }  
    }  
  }