75. Sort Colors

Sort an array of only 0s, 1s, and 2s in place. The Dutch National Flag partition does it in a single pass with three pointers — no counting array, no sort.

● MediumTwo PointersDutch National FlagTypeScript

PROBLEM What we're solving

The array holds only three distinct values — 0, 1, 2. Sort it in place so all 0s come first, then all 1s, then all 2s. nums=[2,0,2,1,1,0] → [0,0,1,1,2,2]. The challenge: do it in one pass and O(1) extra space.

KEY IDEA Three regions, one moving scanner

Insight → maintain three growing regions with three indices. [0, low) is settled 0s, [low, mid) is settled 1s, (high, end] is settled 2s, and [mid, high] is the unknown region. mid scans forward, shrinking the unknown band from the left (on 0/1) or from the right (on 2) until it is empty.

RECIPE Scan with mid, swap the value home

0 · Init. low = mid = 0, high = n - 1. Loop while mid ≤ high— that's the unknown region.
1 · See a 0. Swap nums[low] with nums[mid], then low++ and mid++. The swapped-in value at mid is already scanned (it was a 1 or empty), so mid may advance.
1 · See a 1. It belongs in the middle band — just mid++.
2 · See a 2. Swap nums[mid] with nums[high], then high--. Do NOT advance mid — the value just pulled in from high is unscanned and must be re-checked.

Classic confusion → why advance mid on a 0-swap but not on a 2-swap? Because low ≤ mid always, so the cell you swap from low was already examined (it can only be a 1). But high sits in unexplored territory, so the incoming value is fresh — leave mid put and look again.

COST Complexity & alternatives

Counting sort (two passes)

O(n) · 2 passes

Count 0/1/2, then overwrite. Correct but reads twice.

Dutch National Flag

O(n) · 1 pass

O(1) extra space, in place, single scan.

Space note

Both are O(n) time, but the flag partition touches each element at most once and uses only three index variables → strictly O(1) extra space in a single pass. A generic comparison sort would be O(n log n) — needlessly slow when there are only three keys.

Pattern transfer → the three-way partition is exactly the partition step of 3-way quicksort(handles duplicate pivots), and the low/mid/high invariant generalizes to any "bucket values into < pivot / = pivot / > pivot" problem.

RUN IT Dutch National Flag — one-pass three-way partition

nums =

step 0 / 7

STARTThree pointers: low=0, mid=0, high=5. Scan with mid while mid ≤ high.

1function sortColors(nums: number[]): void {
2  let low = 0;          // boundary: everything left of low is 0
3  let mid = 0;          // scanner / unknown frontier
4  let high = nums.length - 1; // boundary: everything right of high is 2
5 
6  while (mid <= high) {
7    if (nums[mid] === 0) {            // 0: send left
8      [nums[low], nums[mid]] = [nums[mid], nums[low]];
9      low++; mid++;
10    } else if (nums[mid] === 1) {     // 1: already home
11      mid++;
12    } else {                          // 2: send right, re-check mid
13      [nums[mid], nums[high]] = [nums[high], nums[mid]];
14      high--;
15    }
16  }
17}

nums2lo·mid012213140hi

State

low

mid

high

0 (low region)1 (middle)2 (high region)

slowfast

TYPESCRIPT The solution, annotated

sortColors.ts
function sortColors(nums: number[]): void {
  let low = 0;          // boundary: everything left of low is 0
  let mid = 0;          // scanner / unknown frontier
  let high = nums.length - 1; // boundary: everything right of high is 2

  while (mid <= high) {
    if (nums[mid] === 0) {            // 0: send left
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {     // 1: already home
      mid++;
    } else {                          // 2: send right, re-check mid
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Reading it block by block

Lines 2–4 — the three invariants. Everything before low is 0, everything after high is 2, and [mid, high] is still unknown. low and mid both start at 0; high at the last index.

Line 6 — loop condition. Continue while mid <= high. Once they cross, the unknown region is empty and the array is fully partitioned.

Lines 7–9 — value is 0. Swap it down to the 0-region boundary, then advance low and mid together. The cell coming from low was already scanned, so it is safe to move mid past it.

Lines 10–11 — value is 1. It already sits in the middle band; nothing to swap, just mid++.

Lines 12–14 — value is 2. Swap it up to the 2-region boundary and shrink with high--. Crucially mid stays put: the value pulled in from high has never been examined.

Complexity → O(n) time — each step advances mid or retreats high, so the loop runs at most n times. O(1) extra space (three indices). Single in-place pass.

INTERVIEWFollow-ups they'll ask

"Why not just count and rewrite?" A counting pass is also O(n) and easy to explain, but it reads the array twice; the flag partition is a single pass — bring it up as the tighter alternative.
"What if mid advanced after the 2-swap?" You could skip an unscanned value (e.g. another 2 or a 0) and leave the array unsorted. Walk through [2,2] to show the bug.
"Generalize to k colors?" Dutch flag is specific to 3 buckets; for k keys use counting sort (O(n + k)) or repeated partitioning.
"Stability?" This partition is not stable — equal elements may be reordered by swaps. Counting sort can be made stable if order matters.

OPTIMAL Two Pointers

sortColors.ts
function sortColors(nums: number[]): void {
  let low = 0;          // boundary: everything left of low is 0
  let mid = 0;          // scanner / unknown frontier
  let high = nums.length - 1; // boundary: everything right of high is 2

  while (mid <= high) {
    if (nums[mid] === 0) {            // 0: send left
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {     // 1: already home
      mid++;
    } else {                          // 2: send right, re-check mid
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Complexity → O(n) time — each step advances mid or retreats high, so the loop runs at most n times. O(1) extra space (three indices). Single in-place pass.

ALT 1 Counting sort — two passes

O(n) time · O(1) space

Count how many 0s, 1s, and 2s there are, then overwrite the array in order. Simplest correct idea, but it reads the array twice instead of partitioning in one pass.

approach-2.ts
function sortColors(nums: number[]): void {
  const count = [0, 0, 0];
  for (const v of nums) count[v]++;        // pass 1: tally
  let i = 0;
  for (let c = 0; c <= 2; c++) {           // pass 2: rewrite
    for (let k = 0; k < count[c]; k++) nums[i++] = c;
  }
}

Note → Clear and O(n), but it makes two passes and overwrites rather than swapping. The Dutch National Flag partition does the same work in a single in-place scan.

MNEMONIC The one-liner

"0 swaps with low (both ++), 1 just mid++, 2 swaps with high (high-- only)."

TRIGGERS When you see _ → reach for _

array of only 0/1/2 (or 3 keys)	Dutch National Flag partition
"sort in place, one pass, O(1)"	low / mid / high pointers
< pivot / = pivot / > pivot	3-way partition (quicksort)
on a 2-swap, recheck same index	advance high only, not mid

SKELETON The reusable shape

skeleton.ts
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
  if (nums[mid] === 0) {
    [nums[low], nums[mid]] = [nums[mid], nums[low]];
    low++; mid++;
  } else if (nums[mid] === 1) {
    mid++;
  } else {                       // === 2
    [nums[mid], nums[high]] = [nums[high], nums[mid]];
    high--;                      // DON'T advance mid
  }
}

FLASHCARDS Tap to flip

What do low, mid, high represent?

[0,low) = settled 0s, [low,mid) = settled 1s, (high,end] = settled 2s, [mid,high] = unknown.

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is done when nums[mid] === 0?

QUESTION 02

When nums[mid] === 2, why does mid NOT advance?

QUESTION 03

What is the loop condition?

QUESTION 04

Time and space complexity?

QUESTION 05

After running on [2,0,2,1,1,0], the result is:

QUESTION 06

Why is this preferred over a generic comparison sort here?

QUESTION 07

If you mistakenly did mid++ after the 2-swap, what breaks?

QUESTION 08

#75 · Sort ColorsSort an array of 0s, 1s, and 2s in a single pass with Dijkstra's Dutch National Flag: low/mid/high pointers partition the array into three regions, swapping 0s to the front and 2s to the back as mid scans.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Three regions, one moving scanner

RECIPE Scan with mid, swap the value home

COST Complexity & alternatives

Space note

RUN IT Dutch National Flag — one-pass three-way partition

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Two Pointers

ALT 1 Counting sort — two passes

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _