Sort Colors

MEDIUM✓ CHIP-TIMEDLC #75 — FULL STATEMENT ↗

The drill: Sort an array holding only three distinct values into ascending order, in place, in one pass, without counting into buckets first.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array holds only three distinct values, standing in for three colors, and the job is to rearrange it into ascending order — in place, without allocating a second array.

A first pass that counts how many of each value exist and then rewrites the array would work, but the real target here is doing the sort in a single pass over the array.

The three values may appear in any starting order and in any quantities, including zero of a given value — the finished array just needs every 0 before every 1 before every 2.

EX 01

nums = [2, 0, 2, 1, 1, 0]

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

EX 02

nums = [2, 0, 1]

→ [0, 1, 2]

MINIMUM INTERESTING SIZE

EX 03

nums = [0]

→ [0]

SINGLE ELEMENT, ALREADY SORTED

arrays hold only the three values 0, 1, and 2, mixed in any proportion
up to a few thousand elements
sorting happens in place — no second array
a single pass is the target, though a two-pass counting sort is also correct

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Counting how many 0s, 1s, and 2s appear and rewriting the array from those counts already sorts it correctly — but it takes two full passes. Can one pass do both the counting and the placing?

HINT 2 THE STRUCTURE

Three regions need to exist inside the same array at once: 0s at the front, 2s at the back, 1s settling in the middle. Three pointers can track the boundaries of those regions as you go.

HINT 3 ONE STEP FROM THE ANSWER

Keep low, mid, high pointers. If nums[mid] is 0, swap it to low and advance both; if 2, swap it to high and pull high back without advancing mid; if 1, just advance mid — mid has already inspected everything to its left.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE DUTCH FLAG SWEEPPATTERN · DUTCH NATIONAL FLAGnums = [2, 0, 2, 1, 1, 0]

STEP 1

low = mid = 0, high = 5. mid scans forward: 0s sort to the front, 2s sort to the back, 1s stay put.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/sort-colors.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 13 LN

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        counts = [0, 0, 0]
        for x in nums:
            counts[x] += 1
        i = 0
        for color in range(3):
            for _ in range(counts[color]):
                nums[i] = color
                i += 1

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                int tmp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = tmp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int tmp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = tmp;
                high--;
            }
        }
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 21 LN

class Solution {
    public void 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 k = 0; k < counts[color]; k++) {
                nums[i++] = color;
            }
        }
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED