Leetcode: Sort Colors

This question is asked both at Microsoft and Amazon. It is called "Sort Colors". The question is as follows: 

Given an array nums with n objects colored red, white, or blue, sort them in place so that objects of the same color are adjacent and we use 0,1,2 to represent red, white, and blue. Here are some examples:

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

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

Example 1:

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]

Output: [0,1,2]

Example 3:

Input: nums = [0]

Output: [0]

Example 4:

Input: nums = [1]

Output: [1]

 

Constraints:

n == nums.length

1 <= n <= 300

nums[i] is 0, 1, or 2.

The approach here is the one-pass approach. This problem is the national flag problem. We want to get from 202110 to 001122. We want to have 2 pointers: p0, the rightmost boundary of 0s, and p2, the leftmost boundary of 2s. 

Afterward, we initialize the index of an element to consider, if nums[curr] == 0, we swap curr and p0 elements, and move both pointers to the right, otherwise if equal to 2 swaps the curr and the p2 elements. Otherwise, just move the pointer to the right.

This is actually a dual-pivot partitioning subroutine of the quicksort algorithm.

public void sortColors(int[] nums) {

    int lo = 0, hi = nums.length - 1, u = 0;

    while(i <= hi) {

        if(nums[i] == 0) swap(nums, lo++, i++);

        else if(nums[i] == 2) swap(nums, i, hi--);

        else if (nums[i] == 1) i++;

    }

} 

private void swap(int[] nums, int i, in j) {

    int t = nums[i];

    nums[i] = nums[j];

    nums[j] = t;

}