leetcode: Sort Colors

Problem Description:

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.

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?

Solution and Precautions:

By keeping three pointers, i (=0),  j (= n -1), k, i points to the front part of the array while j points to the back end of the array, use k to scan through the whole array, when encountering 0, swap A[i] and A[k], when encountering 2, swap A[j] and A[k] and move the pointers i, j, k correspondingly, after finishing one pass scan, all the elements before i are expected to be 0, all the elements after j are expected to be 2, all the elements between i and j are 1.

Tips and Divergent thinking:

Be careful when moving the pointers: when to just move j e.g j–, when to just move i e.g. i++, when to just move k, k++, when to move both i and k, or move both j and k.

Written on May 20, 2013