Given an array 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.

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

Note: You are not suppose to use the library’s sort function for this problem.

Example:

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

We will use counting sort. Counting sort works for array of integers and will use a size k aux array, k is the number of different kinds of integer in the array. The aux array will store the frequency of the integers

Table of Contents

Two pass algorithm

Use standard counting sort

    void sortColors(vector<int>& nums) {
        std::vector<int> freq(3, 0);
        for(int i = 0; i < nums.size(); i ++){
            freq[nums[i]] += 1;
        }

        int pos = 0;
        for(int i = 0; i < freq.size(); i ++){
            for(int j = pos; j < freq[i] + pos; j ++){
                nums[j] = i;
            }
            pos += freq[i];
        }
    }

We first record the freq of each integer. Then we iterate through frequencies list and for each frequency about number x, we will fill the number list with x from [pos, pos + freq of x].

bugs

I was using a position to record the current position. But forgot to update it properly; I just assign pos = freq[i] instead of adding.When we use a position counter in a for loop, but not incremented by a for loop, that counter is usually accumulated through +=

one pass algorithm

Ideas

We have three colors, we the sorted array will have the form [0,0,0,0….1,1,1,1…2,2,2,2]. We will use 3 ptrs to partition the solutions

3 ptrs, 4 intervals

Ptr0, left of this pts is 0. [begin, Ptr0) are all 0
Ptr1, [Ptr0, Ptr1) are all 1
Ptr2, (Ptr2, end] are all 2. also [Ptr1, Ptr2] are unknown

We have 4 intervals and the goal is to “squeeze out” the unknown and keep the other three in order.

[0,0,0,0,1,1,1,1,1,1,1,     2,2,2,2,2]
         ^           ^      ^
        ptr0        ptr2   ptr1

We can see that [begin, ptr0) are all 0, [ptr0, ptr1) are all 1, (ptr2, end] are all 2. and unknown is empty because ptr2 < ptr1.

Base case for the loop invariant

In the beginning, we initiate Ptr0 = Ptr1 = 0. Ptr2 = end.
We have all 0 in [begin, 0) = empty, all 1 in [0, 0) = empty, all 2 in (end,end] = empty. Also the unknowns are in [ptr1, ptr2] = whole array.

Iteration step of the loop invariant

Goal of iteration and terminating condition

The goal is to squeeze out the unknown in [ptr1, ptr2]. So we use ptr1 as the iterating pointer and the termination condition is ptr1 > ptr2.
We should keep the 4 intervals consistent.

if nums[ptr1] == 0

We will swap nums[ptr0] with nums[ptr1] and increment both ptr0 and ptr1.
Before

    [0,0,0....,0,1,1,1,1,1,1,0, ...]
                 ^           ^     
                ptr0        ptr1

Before we swap, we know what’s on nums[ptr0] must be a 1 because [ptr0,ptr1) are all 1. So we need to

put the 0 found in nums[ptr1] to nums[ptr0] and increment ptr0 so [begin, ptr0) are all 0.
Put the 1 that was in nums[ptr0] in nums[ptr1] and increment ptr1 to maintain [ptr0, ptr1) are all 1

After

    [0,0,0....,0,0,1,1,1,1,1,1,unknown ...]
                   ^             ^     
                  ptr0          ptr1

if nums[ptr1] == 1

We just increment ptr1 by 1 so [ptr0, ptr1) are all 1 and ptr1 points to another unknown

If nums[ptr1] == 2

before

[1,1,1,1,1,1  ,2,unkonwn,unkonwn...2,2,2,2,2]
               ^            ^
             ptr1          ptr2

We want to put the 2 in nums[ptr2] and also don’t want to lose any entry, so we swap ptr1 with ptr2.
After the swap, ptr2 will point to 2 so we need to decrement (move ptr2 toward begin) ptr2.
But ptr1 still points to unknown so we don’t move ptr2.

AFter

[1,1,1,1,1,1  ,unknown,unkonwn,2...2,2,2,2,2]
                 ^           ^
               ptr1          ptr2

In the end, ptr1 will cross ptr2 and we have put all the unknown into the right place.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int ptr0 = 0;                 //left of ptr is all 0
        int ptr1 = 0;                 //btw ptr0, ptr1 is 1
        int ptr2 = nums.size() - 1;   //right of ptr are all 2
        //undefined(unsorted) nums are btween ptr1 and ptr2

        while(ptr1 <= ptr2){// still have undefined numbers
            if(nums[ptr1] == 0){
                int temp = nums[ptr1];
                nums[ptr1] = nums[ptr0];
                nums[ptr0] = temp;
                //after swap, increment both 
                ptr0 ++;
                ptr1 ++;
            }
            else if(nums[ptr1] == 1){
                ptr1 ++;
            }
            else{
                int temp = nums[ptr1];
                nums[ptr1] = nums[ptr2];
                nums[ptr2] = temp;
                ptr2 --;
            }

        }
    }      
};

Take away,

When you see the input is integral and we want to sort them, think counting sort.

LC75. Sort Colors