Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo

The problem, simply

You get an array where every number is 0, 1 or 2. Rearrange it in place so all 0s come first, then all 1s, then all 2s. Do not call a sorting function.

The famous version walks the array only once. It is called the Dutch national flag problem, because the flag has three stripes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count how many 0s, 1s and 2s there are. Then write that many 0s, then 1s, then 2s.

1. Walk once and count each value.
2. Walk again and overwrite the array.

class Solution {
    public void sortColors(int[] arr) {
        int[] count = new int[3];
        for (int x : arr) count[x]++;              // how many of each
        int i = 0;
        for (int v = 0; v < 3; v++) {
            for (int c = 0; c < count[v]; c++) arr[i++] = v;   // write them back in order
        }
    }
}

How long it takes: two walks, O(n). Extra room: three counters, O(1). This is a perfectly good answer. Interviewers then ask: can you do it in one walk? And it only works because the items are plain numbers. If each item were a record with a color plus other data, overwriting would lose the data.

Way 2: the clever way

Keep three fingers and four zones:

• 0 .. low - 1: all 0s.
• low .. mid - 1: all 1s.
• mid .. high: not looked at yet.
• high + 1 .. n - 1: all 2s.

Look at arr[mid]:

1. It is 0: swap it with arr[low]. Move low and mid right.
2. It is 1: move mid right.
3. It is 2: swap it with arr[high]. Move high left, but not mid, because the box that came from high has not been looked at yet.

Stop when mid > high.

class Solution {
    public void sortColors(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) {
                swap(arr, low++, mid++);       // 0 goes to the front zone
            } else if (arr[mid] == 1) {
                mid++;                         // 1 is already in the middle zone
            } else {
                swap(arr, mid, high--);        // 2 goes to the back zone, check mid again
            }
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

How long it takes: each step either moves mid right or high left, so at most n steps, one walk, O(n). Extra room: three fingers, O(1).

Why can mid move after a swap with low? Everything between low and mid - 1 is a 1, so the box that comes back from low is a 1 (or the same 0, when low == mid). It is already checked.

Watch out for

• The loop condition is mid <= high, not mid < high. The box at high itself still needs a look.
• Swapping with low but forgetting to move mid too can make mid fall behind low.
• The order of the if checks does not matter, but each loop turn must handle exactly one box.

What interviewers ask next

• Is it stable (do equal items keep their order)? No. Swaps jump items over others. If stability matters, use counting with an output array.
• Partition around a pivot value p into less than, equal and greater (three way partitioning)? Same code, with "less than p" instead of 0 and "greater than p" instead of 2. It is the heart of quicksort with many repeated keys.
• Four colors? Counting still works. In one walk, you can keep four zones with more fingers, but counting is simpler.
• Move all negative numbers before the positive ones? The two zone version of the same idea: one finger for the next negative spot.

Remember this

Grown-up words: the fingers are three pointers, the zones are loop invariants, the whole thing is Dijkstra's Dutch national flag algorithm (three way partitioning), and Way 1 is counting sort.