72. Sort Colors

There are only three possible values — 0, 1, and 2 — so we don't need a comparison sort. If we know how many of each color we have, we can paint the array back in order.

Approach

1. First pass: count the occurrences of 0, 1, and 2.
2. Second pass: overwrite nums — first c0 zeros, then c1 ones, then c2 twos.

Walk-through

nums = [2, 0, 2, 1, 1, 0] → counts {0: 2, 1: 2, 2: 2} → write [0, 0, 1, 1, 2, 2].

Complexity

• Time: O(n) — two linear passes.
• Space: O(1) — three integer counters.

import java.util.*;

class Solution {
    public int[] sortColors(int[] nums) {
        int[] counts = new int[3];
        for (int x : nums) counts[x]++;
        int i = 0;
        for (int color = 0; color < 3; color++) {
            for (int c = 0; c < counts[color]; c++) {
                nums[i] = color;
                i++;
            }
        }
        return nums;
    }
}

We can do it in a single pass by maintaining three regions: a left zone of confirmed 0s, a middle zone of confirmed 1s, and a right zone of confirmed 2s. Two pointers lo and hi mark the unsorted middle, and a cursor i walks through it placing each value in the right zone.

The mental picture

Think of the array as four regions, in order from left to right:

[ 0 0 0 | 1 1 1 | ? ? ? ? | 2 2 2 ]
        lo      i         hi

• Everything before lo is a confirmed 0.
• Everything from lo up to i - 1 is a confirmed 1.
• Everything from i to hi is unprocessed (unknown).
• Everything after hi is a confirmed 2.

We walk i through the unknown region. Each step, we look at nums[i] and slot it into the correct region.

The three rules at index i

1. nums[i] == 0 — it belongs at the left. Swap with nums[lo], then lo += 1, i += 1.
   • The value coming out of nums[lo] was either a 1 (in the 1-region) or lo == i so we just swapped with ourselves. Either way it's safe to advance i.
2. nums[i] == 1 — already in the 1-region. Just i += 1.
3. nums[i] == 2 — it belongs at the right. Swap with nums[hi], then hi -= 1. Do not advance i — the value we just pulled in from nums[hi] is unknown, so we have to inspect it on the next iteration.

Stop as soon as i > hi: at that point the unknown region is empty.

Walk-through

nums = [2, 0, 2, 1, 1, 0], start lo=0, i=0, hi=5.

Sorted in one sweep.

Why we don't advance i after a 2-swap

When we swap nums[i] with nums[hi], the value coming back into position i came from the unknown region — we have not classified it yet. If we blindly advanced i we could leave a stray 0 or 2 in the middle. By keeping i put, the next loop iteration inspects the new value.

Edge cases

• All same color (e.g. [1,1,1]): rule 2 fires for every position, lo never moves, hi never moves, but the array is already correct.
• n == 1: loop exits immediately.

Complexity

• Time: O(n) — i + (n - 1 - hi) only ever increases, and each iteration bumps at least one of those.
• Space: O(1) — fully in-place.