LC75. Sort Colors

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

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

  1. Ptr0, left of this pts is 0. [begin, Ptr0) are all 0
  2. Ptr1, [Ptr0, Ptr1) are all 1
  3. 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

  1. put the 0 found in nums[ptr1] to nums[ptr0] and increment ptr0 so [begin, ptr0) are all 0.
  2. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax