Leetcode 75. Sort Colors

Description:

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.

Thinking:

A rather straight forward solution is to use counting sort. However, since we only have 3 colors. We can come up with a one pass algorithm, which main idea is to swap 0 in the begin and 2 in the end.

Complexity:

The time complexity is O(n);

Step:

1. check whether input is valid.
2. Use two pointer, left and right, to indicate the current position that we should put 0 and 2 in.
3. Do a loop from 0 to right.

   Code:
   

   public class Solution {
    public void sortColors(int[] nums) {
        int i = 0, left = 0, right = nums.length-1;
        while(i <= right){
            if(nums[i] == 0){
                swap(nums, i, left);
                left++;
                i++;
            }
            else if(nums[i] == 2){
                swap(nums, i, right);
                right--;
            }
            else{
                i++;
            }
        }
    }
    private void swap(int[] nums, int i, int j){
         int temp = nums[i];
         nums[i] = nums[j];
         nums[j] = temp;
    }
   }
   

   Conclusion:
   

   We should note that we don't i++ when nums[i] == 2. Since we don't know the number we swap from right is 0,1 or 2. However, we definitely know that the number we swap from left must 1, since if the number 0 or 2, it must have already done the process of swapping.