LeetCode 75 Sort Colors

Given an array with n objects colored red, white or blue, sort them 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.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

Difficulty
Medium

Similar Problems
[LeetCode 148] Sort List M [LeetCode 280] Wiggle Sort M [LeetCode 324] Wiggle Sort II M

Analysis

Idea 1

Counting Sort Since we know the value range of all elements, we can use counting sort to solve this problem. The defact is that we need to scan the array twice, one for counting, one for filling the array with the elements.

Idea 2

Double indexsers Left indexer tracks 0, right indexer tracks 2. Use index cur to iterate over the array, if encounters 0, swap it with the element at left indexer, left++, if encounters 2, swap it with the element at right indexser, right--, otherwise, cur++.

Idea 3 Take advantage of the partition idea from quick sort, use 1 as the pivot and move 0 to its left, move 2 to its right. This is similar to double indexsers method.

Solutions

1. Cpp solution

Counting Sort

class Solution {
public:
    void sortColors(vector<int> &A) {
        const int cnum = 3;
        int counts[cnum] = { 0 };      // record the number of times that a color has appeared
        for (int i = 0; i < n; i++)
            counts[A[i]]++;
        for (int i = 0, index = 0; i < cnum; i++)
            for (int j = 0; j < counts[i]; j++)
                A[index++] = i;
    }
};

2. Cpp solution

Double indexsers

class Solution {
public:
    void sortColors(vector<int> &A) {
        int red = 0, blue = n - 1, cur = 0;
        while(cur <= blue){
            if(A[cur] == 0) swap(A[cur++], A[red++]);
            else if(A[cur] == 2) swap(A[cur], A[blue--]);
            else cur++;
        }
    }
};

3. Cpp solution

use cpp std library: equal_to, bind1st or bind2nd

class Solution {
public:
    void sortColors(int A[], int n) {
        partition(partition(A, A + n, bind1st(equal_to<int>(), 0)), A + n,
                    bind1st(equal_to<int>(), 1));
    }
};

or

class Solution {
public:
    void sortColors(int A[], int n) {
        partition(partition(A, A + n, bind2nd(equal_to<int>(), 0)), A + n,
                    bind2nd(equal_to<int>(), 1));
    }
};

4. Cpp Solution

A fined partition function using c++11 std library

Explanations: partition function will place elements to the left part of the container if pred returns true, the returned index is the index of the first element of the right part.

class Solution {
public:
    void sortColors(int A[], int n) {
        partition(partition(A, A + n, bind1st(equal_to<int>(), 0)), A + n,
        bind1st(equal_to<int>(), 1));
    }
private:
    template<typename ForwardIterator, typename UnaryPredicate>
    ForwardIterator partition(ForwardIterator first, ForwardIterator last, UnaryPredicate pred){
        auto pos = first;
        for (; first != last; ++first)
            if (pred(*first))
                swap(*first, *pos++);
        return pos;
    }
};

5. Go solution

func sortColors(nums []int) {
    n := len(nums)

    left, right, i := 0, n-1, 0
    for i <= right {
        if nums[i] == 0 {
            nums[left], nums[i] = nums[i], nums[left]
            left++   // note here, since we start both i and left from 0, we need to step forward both of them  
        } else if nums[i] == 2 {
            nums[i], nums[right] = nums[right], nums[i]
            right--
        } else {
            i++
        }
    }
}

Reference