Picker totes come off the belt tagged 0, 1, or 2 for three chutes. The belt array has to land grouped — all 0s, then 1s, then 2s — in the same slots, before the diverter fires. The intern counted each tag and rewrote the array left to right. A hundred totes were fine. The board then forbade the second pass and forbade Arrays.sort: three values, one walk, swaps only.

Sort Colors asks for a 0, then 1, then 2 partition, in place. An array already gives nums[i] for free. Counting then rewriting uses that and still takes two passes. A comparison sort ignores the domain and pays O(n log n) for a question three pointers answer in one.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the left/right walk. Here a third index classifies the unknown middle. The same three-way split is the partition step inside quicksort; the keys are only 0, 1, and 2, so one pass finishes the array and you stop.

The problem

Given an int[] nums whose values are only 0, 1, and 2, reorder it in place so every 0 comes first, then every 1, then every 2. Do not allocate a second array of n. Do not call a general-purpose sort.

[1, 2, 0, 2, 1, 0]  →  [0, 0, 1, 1, 2, 2]
[2, 2, 1]           →  [1, 2, 2]
[0, 1, 0]           →  [0, 0, 1]

Note: Stability is not required. Equal values may change order. The prompt is the three runs, not a key-preserving sort. Values outside {0, 1, 2} are outside the spec; at the board, ask.

Count, then rewrite — or sort the whole array

Tally how many 0s, 1s, and 2s, then overwrite left to right. Correct. Two passes, O(1) extra counters. Arrays.sort(nums) is also correct and the wrong primitive: it does not use that the domain has three values.

void sortColorsCount(int[] nums) {
    int z = 0, o = 0, t = 0;
    for (int x : nums) {
        if (x == 0) {
            z++;
        } else if (x == 1) {
            o++;
        } else {
            t++;
        }
    }
    int i = 0;
    for (int k = 0; k < z; k++) {
        nums[i++] = 0;
    }
    for (int k = 0; k < o; k++) {
        nums[i++] = 1;
    }
    for (int k = 0; k < t; k++) {
        nums[i++] = 2;
    }
}

At n = 20 this is a rounding error. The complaint is the second write, and the sort’s extra log n. One pass of swaps already answers: 0 left, 2 right, or a 1 in the middle?

Three pointers: low, mid, high

Interviewers call this the Dutch national flag walk: three values, three indexes. lo is the next slot a 0 should occupy. hi is the next slot a 2 should occupy. mid walks the unknown slice lo..hi.

  • nums[mid] == 0: swap with lo, then lo++ and mid++. The inbound value at lo was already classified (a 1, or another 0).
  • nums[mid] == 1: mid++. It belongs in the middle run.
  • nums[mid] == 2: swap with hi, then hi--. Do not advance mid. The inbound value from hi has not been classified yet.
[1, 2, 0, 2, 1, 0]   lo=0  mid=0  hi=5

1 → mid++                          [1, 2, 0, 2, 1, 0]
2 → swap mid/hi, hi--              [1, 0, 0, 2, 1, 2]
0 → swap mid/lo, lo++, mid++       [0, 1, 0, 2, 1, 2]
0 → swap mid/lo, lo++, mid++       [0, 0, 1, 2, 1, 2]
2 → swap mid/hi, hi--              [0, 0, 1, 1, 2, 2]
1 → mid++   mid > hi, stop         [0, 0, 1, 1, 2, 2]

The Java is that walk:

void sortColors(int[] nums) {
    int lo = 0;
    int mid = 0;
    int hi = nums.length - 1;
    while (mid <= hi) {
        if (nums[mid] == 0) {
            int tmp = nums[lo];
            nums[lo] = nums[mid];
            nums[mid] = tmp;
            lo++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int tmp = nums[mid];
            nums[mid] = nums[hi];
            nums[hi] = tmp;
            hi--;
        }
    }
}

Time is O(n) — one pass, constant work per index. Extra space is O(1) — three indexes and a temp. The count-and-rewrite is the same extra space and two passes; say so, then do the swaps when they want one walk.

Note: The loop condition is mid <= hi, not mid < nums.length. Everything after hi is already a 2. If you increment mid after swapping in a 2, you skip an unclassified value and a 0 can land in the right run.

What interviewers usually poke next

  • Only two values, 0 and 1. Then two pointers, no middle index. Same partition, thinner.
  • k colors. Three pointers do not grow into k pointers. Count then rewrite is O(n + k) and the honest bill. Do not start a sort lecture.
  • Why mid stays after a 2. The swapped-in value came from the unknown right. Walk it on the next iteration.
  • Empty or all one color. lo, mid, and hi still terminate. All 1s never swap. All 2s shrink hi until it meets mid.

You are done with this problem when you can walk [1, 2, 0, 2, 1, 0] on a whiteboard with three indexes, and you can say out loud why counting is two passes, why Arrays.sort is the wrong primitive, and why mid does not move after a swap with hi.