Sort Colors

Approach Summary

Dutch National Flag algorithm: three-way partition with lo, mid, hi pointers. Swap to move 0s left, 2s right.

Full Solution & Approach

The array contains only three distinct values — 0, 1, 2 — so a counting sort is allowed, but the problem explicitly asks for a one-pass in-place solution, which is the Dutch National Flag algorithm. Maintain three regions with three pointers: everything before lo is 0, everything after hi is 2, and mid scans the middle. While mid does not pass hi, inspect nums[mid]. If it is 0, swap it with nums[lo] and advance both lo and mid — a 0 has been locked into the left region. If it is 1, it is already in the correct region, so just advance mid. If it is 2, swap it with nums[hi] and decrement hi, but do NOT advance mid — the value swapped into mid from the right region is unexamined and must be processed on the next iteration. The three regions never overlap and every swap places at least one element in its final region, so the loop runs in O(n) with only constant extra space. The pattern generalizes to any k-way partitioning and is the canonical implementation of the quick-sort three-way partition used to sort arrays with many duplicate keys.

Each iteration either advances mid or shrinks the hi region, so the loop runs at most n times — O(n) time. Only three index variables, so O(1) space.

Solution Code

Solution

def sort_colors(nums: list[int]) -> None:
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1

function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;
  while (mid <= hi) {
    if (nums[mid] === 0) {
      [nums[lo], nums[mid]] = [nums[mid], nums[lo]];
      lo++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[hi]] = [nums[hi], nums[mid]];
      hi--;
    }
  }
}

public void sortColors(int[] nums) {
    int lo = 0, mid = 0, 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--;
        }
    }
}

void sortColors(vector<int>& nums) {
    int lo = 0, mid = 0, hi = (int)nums.size() - 1;
    while (mid <= hi) {
        if (nums[mid] == 0) {
            swap(nums[lo], nums[mid]);
            lo++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[hi]);
            hi--;
        }
    }
}

Edge Cases to Watch

All zeros or all twos — the pointer regions still partition correctly
Single element — no swaps needed
Already sorted — the algorithm still makes a full pass
Mixed pattern like 2,0,2,1,1,0 — the mid-not-advancing step after a 2-swap is what makes it correct

How to Recognize This Pattern

In-place sort of array with only 3 distinct values
"Sort 0s, 1s, 2s in one pass"

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)