Sort Colors

Question (LC.75)

Given an array of objects, group them into red, white and blue.

Example

I: [1, 0, 1, 2]
O: [0 | 1, 1 | 2]

Counting Sort

We can use an array to map the frequencies of each color and then unmap them to the input array.

public void sortColors(int[] nums) {
    int[] map = new int[3];
    // map the frequencies
    for (int num: nums) map[num]++;
    // unmap the frequencies
    for (int i = 0; i < map[0]; i++) nums[i] = 0;
    for (int j = 0; j < map[1]; j++) nums[j + map[0]] = 1;
    for (int k = 0; k < map[2]; k++) nums[k + map[0] + map[1]] = 2;
}

Time O(n) Space O(1) but not in-place

3-Group Partition