Array Sorting Binary Search Two Pointers
Intermediate Level

Implement the sortColorsOnePass method that sorts three color values in one pass.

The input contains an array nums and its length size. The array contains only three values: 0, 1, and 2.

Your task is to reorder the array so that all 0 values come first, followed by all 1 values, and then all 2 values.

For example, [2,0,2,1,1,0] should become [0,0,1,1,2,2].

Example 1
Input:
nums (int[]) = [2,0,2,1,1,0]
size (int) = 6
Return:
(int[]) [0,0,1,1,2,2]
Example 2
Input:
nums (int[]) = [2,0,1]
size (int) = 3
Return:
(int[]) [0,1,2]
Example 3
Input:
nums (int[]) = [0]
size (int) = 1
Return:
(int[]) [0]

Use the Dutch National Flag one-pass algorithm.

Maintain three areas: values before low are already 0, values after high are already 2, and mid scans the unknown area.

When nums[mid] is 0, swap it to the front. When it is 2, swap it to the back. When it is 1, just move forward.

Pseudocode:

function sortColorsOnePass(nums, size):
    low = 0
    mid = 0
    high = size - 1
    while mid <= high:
        if nums[mid] == 0:
            swap nums[low] and nums[mid]
            low++
            mid++
        else if nums[mid] == 1:
            mid++
        else:
            swap nums[mid] and nums[high]
            high--
    return nums
Run your code to see the result.