Sort an array of 0's 1's and 2's

Given an array nums consisting of only 0, 1, or 2. Sort the array in non-decreasing order.

The sorting must be done in-place, without making a copy of the original array.

Brute Force: Sorting#

Apply a general-purpose sort to the array. Since the values are only 0, 1, or 2, any comparison-based sort will produce the correct order, but it does not exploit the very limited value domain and costs O(n log n) — significantly more work than a single pass.

class Solution {
public:
    void sortZeroOneTwo(vector<int>& nums) {
        sort(nums.begin(), nums.end());
    }
};

Time Complexity: O(nlogn)

Space Complexity: O(1)

Better Approach: Store freq of 0s, 1s and 2s#

Since the only possible values are 0, 1, and 2, count the occurrences of each in one pass and then overwrite the array: fill cnt0 zeros, followed by cnt1 ones, followed by cnt2 twos. This requires two passes but runs in O(n) total time with O(1) extra space — already better than sorting. The trade-off is two passes instead of one; the Dutch National Flag algorithm achieves the same result in a single pass.

class Solution {
public:
    void sortZeroOneTwo(vector<int>& nums) {
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) cnt0++;
            else if (nums[i] == 1) cnt1++;
            else cnt2++;
        }

        for (int i = 0; i < cnt0; i++) nums[i] = 0;

        for (int i = cnt0; i < cnt0 + cnt1; i++) nums[i] = 1; 
        
        for (int i = cnt0 + cnt1; i < nums.size(); i++) nums[i] = 2;
    }
};

Time Complexity: O(2*n)

Space Complexity: O(1)

Optimal Approach: Dutch National Flag Algo#

Edsger Dijkstra's Dutch National Flag algorithm partitions the array in a single pass using three pointers: low, mid, and high. The invariant maintained is [0s | 1s | unsorted | 2s]. When nums[mid] is 0, swap it with nums[low] and advance both low and mid. When it is 1, just advance mid. When it is 2, swap it with nums[high] and decrement high (do not advance mid yet, since the swapped element from the right is still unseen). The loop ends when mid > high, at which point the entire array is sorted. One pass, O(1) extra space.

• Divide the array into three regions: [ 0s | 1s | unknown | 2s ]
• And keep expanding these regions while scanning.

class Solution {
public:
    void sortZeroOneTwo(vector<int>& nums) {
        int low = 0, mid = 0, high=nums.size()-1;

        while(mid<=high){
            if(nums[mid]==0){
                swap(nums[low++], nums[mid++]);
            }else if(nums[mid]==1){
                mid++;
            }else{
                swap(nums[mid], nums[high--]);
            }
        } 
    }
};

Time Complexity: O(n)

Space Complexity: O(1)