Sort Colors

MediumThree Pointers · Dutch National Flag🧩 Partitioning & Quickselect LeetCode #75 ↗Updated Oct 30, 2026

Problem

An array nums holds only the values 0, 1 and 2 (red, white, blue). Rearrange it in-place so all 0s come first, then all 1s, then all 2s — without calling a library sort.

Input[2,0,2,1,1,0]Output[0,0,1,1,2,2]

Input[2,0,1]Output[0,1,2]

1 ≤ n ≤ 300 · nums[i] ∈ {0, 1, 2} · Follow-up: one pass with O(1) extra space.

Try it yourself

Java

class Solution {
    public void sortColors(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

With only three keys you can grow the 0-zone from the left and the 2-zone from the right at the same time; whatever stays in the middle is 1. One scan, swaps only.

PatternPartitioning & Quickselect

Instinct Need the k-th smallest/largest, an unordered top-k, or values grouped into buckets in place - partition around a pivot and chase only one side.

Memory hack Pivot, partition, pick a side - quickselect is quicksort's lazy cousin that only chases the half holding k.

Open the Partitioning & Quickselect guide →

Approaches

Brute ForceGeneral Comparison Sort

Time O(n log n)Space O(log n)

Ignore the fact that there are only three values and sort like any integer array (shown here with Arrays.sort, i.e. dual-pivot quicksort; an interviewer will ask you to replace it). Correct, but wastes the tiny key range.

Java

public void sortColors(int[] nums) {
    Arrays.sort(nums);
}

One line and correct, but O(n log n) and violates the “no library sort” rule.

BetterCounting Sort (Two Passes)

Time O(n)Space O(1)

Count how many 0s, 1s and 2s there are, then overwrite the array: that many 0s, then 1s, then 2s. The counts array has fixed size 3, so extra space is constant.

Java

public void sortColors(int[] nums) {
    int[] count = new int[3];
    for (int x : nums) count[x]++;
    int idx = 0;
    for (int color = 0; color < 3; color++) {
        for (int c = 0; c < count[color]; c++) nums[idx++] = color;
    }
}

Linear and simple, but needs two passes over the data.

OptimalDutch National Flag (low / mid / high)

Time O(n)Space O(1)

Invariant: [0, low) = 0s, [low, mid) = 1s, (high, n-1] = 2s, [mid, high] unknown. A 0 is swapped to low; a 2 is swapped to high but mid stays, because the value that arrived from the right is still unchecked.

Java

public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums, low++, mid++);
        else if (nums[mid] == 1) mid++;
        else swap(nums, mid, high--); // don't advance mid
    }
}
private void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

Dry run[2,0,2,1,1,0]

l lowm midh high changed

start
2
l m
0

2

1

1

0
h
nums[m]=2
1
0
l m
0

2

1

1
h
2

swap(m,h), h--
2
0

0
l m
2

1

1
h
2

0: swap(l,m), l++ m++
3
0

0

2
l m
1

1
h
2

0: l++ m++
4
0

0

1
l m
1
h
2

2

2: swap(m,h), h--
end
0

0

1
l
1
h
2
m
2

1,1: m++ → m>h ✔

Single pass, constant space, every element settled once — answers the follow-up.

Pro tip

The same 3-way partition powers quicksort/quickselect on arrays with many duplicates (see Kth Largest Element).

At a glance

Level	Approach	Time	Space
Brute Force	General Comparison Sort	`O(n log n)`	`O(log n)`
Better	Counting Sort (Two Passes)	`O(n)`	`O(1)`
Optimal	Dutch National Flag (low / mid / high)	`O(n)`	`O(1)`

Common pitfalls

Incrementing mid after swapping with high — skips an unchecked value.
Loop condition mid < high instead of mid ≤ high — misses the last element.
Advancing only low on a 0 — the value swapped in is always 1 (or itself), so move both.

Interview tips

Mention counting sort first, then improve to one pass for the follow-up.
State the four-region invariant before writing code.
Trace [2,0,1] to show why mid stays on a high swap.

Pattern

3-way partition (Dutch flag) → group values into <, =, > a pivot (or 3 classes) in one pass.

My notes saved in this browser