Sort an Array of 0s 1s and 2s Using Counting Sort

Problem Statement

Given an array containing only 0, 1, and 2, sort it so all 0s come first, then 1s, then 2s. (This is the "Sort Colors" problem via counting.)

Example

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

Approach

Counting sort for three keys: count how many 0s, 1s, and 2s there are in one pass, then overwrite the array with that many 0s, then 1s, then 2s. A single-pass Dutch National Flag algorithm (three pointers) also solves it in O(n) with one scan.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def sortColors(nums):
    count = [0, 0, 0]
    for x in nums:
        count[x] += 1
    i = 0
    for value in range(3):
        for _ in range(count[value]):
            nums[i] = value
            i += 1
    return nums

Java

void sortColors(int[] nums) {
    int[] count = new int[3];
    for (int x : nums) count[x]++;
    int i = 0;
    for (int value = 0; value < 3; value++)
        while (count[value]-- > 0) nums[i++] = value;
}

C++

void sortColors(vector<int>& nums) {
    int count[3] = {0, 0, 0};
    for (int x : nums) count[x]++;
    int i = 0;
    for (int value = 0; value < 3; value++)
        while (count[value]-- > 0) nums[i++] = value;
}

Key Takeaways

• Counting sort is perfect when there are only a few distinct keys.
• The one-pass Dutch National Flag avoids a second write loop.
• Reference: LeetCode 75 (Sort Colors); CLRS, Ch. 8 (counting sort).