Given an array nums of n integers that are 0, 1, or 2 — representing the colors red, white, and blue — sort it in place so that equal colors are adjacent and ordered 0, 1, 2.
You must mutate the input array directly and return that same array (do not allocate and return a new one). The classic constraint is to do it in one pass with constant extra space, without a library sort.
Example
Two of each color, grouped in order.
Constraints
- n == nums.length
- 1 <= n <= 300
- nums[i] is either 0, 1, or 2.
Intuition
A first pass just counts how many 0s, 1s, and 2s are in the array, then a second pass overwrites the array with that many 0s, followed by that many 1s, then that many 2s.
function sortColors(nums) {
// Tally how many 0s, 1s, and 2s appear — the only three possible values.
const counts = [0, 0, 0];
for (let i = 0; i < nums.length; i++) {
counts[nums[i]]++; // counts[value]++
}
// Second pass: overwrite the array with that many 0s, then 1s, then 2s.
let index = 0;
for (let color = 0; color <= 2; color++) {
for (let copy = 0; copy < counts[color]; copy++) {
nums[index] = color;
index++;
}
}
return nums; // same array instance, now sorted in place
}Counting sort here is already O(n) — the flaw isn't the big-O, it's the shape: it needs two full passes, one to tally every value before it can place anything, and a second to actually write the result. It can't resolve a single element's final position until the whole array has been scanned once. Can we do it in one pass, with no upfront tally?
Since there are only three possible values, we don't need a general comparator at all — track three regions directly instead. Everything before a low pointer is known to be 0s, everything from low up to mid is known to be 1s, and everything after a high pointer is known to be 2s; mid is the only pointer still scanning unexplored territory. It's the Two pointers converge-from-both-ends idea, just widened from two regions to three — the classic Dutch national flag partition.
Each region grows by a single swap: a 0 at mid swaps down to low and, since low's old value is now known to be a 1, mid can safely advance too. A 2 at mid swaps up to high and shrinks the high boundary, but mid must not advance — the value that just moved in from high hasn't been looked at yet. A 1 at mid is already home, so mid just steps forward. One left-to-right pass resolves every element, in place.
Walking it through:
start: low = mid = 0, high = 6
1-no-op: 1 already belongs in the middle region, so mid just steps forward — nothing to swap.
0-swap-left: 0 belongs ahead of low, so swap it there. mid can move forward too — the slot it left behind is now known to hold a 1.
after the 0-swap: low = 1, mid = 2, high = 6
2-swap-right: 2 belongs past high, so swap it up there and shrink the high boundary. mid does NOT advance — the value just swapped in from high is still unexamined.
after the 2-swap: low = 1, mid = 2, high = 5
The value swapped in from high turns out to be a 1 (and so does the next one, at index 3) — two more no-ops, mid just keeps scanning.
Another 0 turns up mid-scan — swap it back to low, same move as before.
after the second 0-swap — scan ends: low = 2, mid = 5, high = 5
mid and high meet at the last 2. The swap is with itself, high drops below mid, and the loop ends — every element resolved into its region in a single pass: [0, 0, 1, 1, 1, 2, 2].
Optimization
Dutch national flag (three pointers)
Keep three pointers: low (next slot for a 0), high (next slot for a 2), and a scanning mid. When nums[mid] is 0, swap it down to low and advance both; when it's 2, swap it up to high and shrink high (don't advance mid — the swapped-in value is unexamined); when it's 1, just advance mid. One pass, in place.
O(n) time, O(1) extra space.
function sortColors(nums) {
let low = 0; // next open slot for a 0, growing from the left
let mid = 0; // scans forward; everything before it is already resolved
let high = nums.length - 1; // next open slot for a 2, growing from the right
while (mid <= high) {
if (nums[mid] === 0) {
// 0 belongs ahead of low — swap it there and grow both regions.
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 2) {
// 2 belongs past high — swap it there and shrink the high boundary.
// Don't advance mid: the value just swapped in from high is unexamined.
[nums[high], nums[mid]] = [nums[mid], nums[high]];
high--;
} else {
// 1 already belongs in the middle region — just move past it.
mid++;
}
}
return nums; // same array instance, now sorted in place
}Complexity analysis
Time complexity: O(n). Here's why:
- Both the counting-sort brute force and the Dutch-flag partition below visit every element a constant number of times, so both are already O(n) — this is a case where the brute force isn't asymptotically slower.
- The three-pointer scan makes exactly one pass: at each step,
mideither advances by one (a 1, or the value just swapped down fromlow) or a swap resolves one more element into its region. - Each of the n elements is examined and placed into its final region in O(1) amortized work.
So both approaches run in O(n) — the optimal solution's advantage is doing it in a single pass with no separate counting phase, not a better big-O.
Space complexity: O(1). Here's why:
- The scan only tracks
low,mid, andhigh— three integers, regardless of the array's length. - All rearranging happens through in-place swaps on the input array itself; no auxiliary array or counts table is built, unlike the brute force's
countsarray (also O(1), but only usable after two full passes).
So the optimal solution uses O(1) auxiliary space — the same asymptotic space as the brute force, but true single-pass in-place rearrangement instead of a count-then-overwrite rebuild.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [0,0] | [0,0] | All-0 pair — smallest all-equal case at the low boundary; every swap the scan makes is a self-swap, since low and mid stay in lockstep. |
| nums = [1,0] | [0,1] | Smallest genuine 0-swap: mid finds a 0 sitting one slot after low, and a single real swap slides it into place. |
| nums = [2,1] | [1,2] | Smallest genuine 2-swap: mid finds a 2 immediately and swaps it up to high, shrinking the high boundary to meet mid; the swapped-in value turns out to be a 1, so mid takes one more no-op step before the scan ends. |
| nums = [2,2] | [2,2] | All-2 pair — smallest all-equal case at the high boundary; high shrinks step by step until it drops below mid and the scan stops. |
| nums = [1,2,0,2,1,0,2,0,1] | [0,0,0,1,1,1,2,2,2] | Nine elements, three of each color, shuffled — exercises repeated 0- and 2-swaps back to back and confirms the single pass still lands every duplicate in its region. |
Try it yourself
Write your solution against the real judge before checking the reference.