Sort three colours in one pass
An array nums holds only the values 0, 1 and 2. Sort it in place in a single pass, using
O(1) extra memory and no library sort, and return it.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 0, 2, 1, 1, 0] | [0, 0, 1, 1, 2, 2] | |
nums = [2, 0, 1] | [0, 1, 2] |
Constraints
- 1 ≤ n ≤ 300
- nums[i] is 0, 1 or 2
Hints
Hint 1
Counting the 0s, 1s and 2s and rewriting the array takes two passes. Can one pass place each value as it is read?
Hint 2
Keep the zeros at the front and the twos at the back as you go. What regions does the array have part-way through?
Hint 3
Use lo, mid and hi: [0, lo) holds 0s, [lo, mid) holds 1s, (hi, n) holds 2s, and [mid, hi] is unread. Look at nums[mid] and decide.
Where people lose marks
- Advancing mid after swapping a 2 to the back: the value swapped in from hi has not been examined and may be a 0 or a 2.
- Looping while mid < hi instead of mid ≤ hi, which leaves the last unread element unexamined.
Dry run on [1,2,0,2,1,0]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums10lo/mid2102231405hilo0mid0hi5
Everything is unread: the window [mid, hi] is the whole array.
-
Step 2 / 8nums10lo/mid2102231405hilo0mid1hi5
nums[mid] = 1: already in the middle region. mid advances.
-
Step 3 / 8nums10lo01mid02231425hilo0mid1hi4
nums[mid] = 2: swap it to position hi = 5; hi moves left. mid stays: the value that came from hi is unread.
-
Step 4 / 8nums00lo11mid022314hi25lo1mid2hi4
nums[mid] = 0: swap it to position lo = 0; lo and mid both advance.
-
Step 5 / 8nums0001lo12mid2314hi25lo2mid3hi4
nums[mid] = 0: swap it to position lo = 1; lo and mid both advance.
-
Step 6 / 8nums000112lo13mid24hi25lo2mid3hi3
nums[mid] = 2: swap it to position hi = 4; hi moves left. mid stays: the value that came from hi is unread.
-
Step 7 / 8nums000112lo13mid/hi2425lo2mid4hi3
nums[mid] = 1: already in the middle region. mid advances.
-
Step 8 / 8nums000112132425lo2mid4hi3
mid has passed hi: nothing is unread, and the array is sorted.
How to think about it
Divide the array into four regions with three pointers:
[0, lo) zeros · [lo, mid) ones · [mid, hi] unread · (hi, n) twos
Look at nums[mid]:
- 0: swap it with
nums[lo], which is a 1 (or the same cell), then advance bothloandmid. - 1: it is already in the right region. Advance
mid. - 2: swap it with
nums[hi]and movehileft. Do not advancemid: the value that arrived fromhihas not been read yet.
Every step shrinks the unread region by one, so the loop ends after at most n steps, when mid > hi.
Dijkstra posed it with the three colours of the Dutch flag; the same partition is the three-way split that makes
quicksort fast on inputs with many equal keys.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def sort_colours(nums):
lo, mid, hi = 0, 0, len(nums) - 1 # [0,lo) 0s, [lo,mid) 1s, [mid,hi] unread, (hi,n) 2s
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 # the value swapped in is still unread
return nums#include <vector>
#include <utility>
std::vector<int> solve(std::vector<int> nums) {
int lo = 0, mid = 0, hi = (int)nums.size() - 1; // [0,lo) 0s, [lo,mid) 1s, [mid,hi] unread, (hi,n) 2s
while (mid <= hi) {
if (nums[mid] == 0) std::swap(nums[lo++], nums[mid++]);
else if (nums[mid] == 1) ++mid;
else std::swap(nums[mid], nums[hi--]); // the value swapped in is still unread
}
return nums;
}class Solution {
public int[] sortColours(int[] nums) {
int lo = 0, mid = 0, hi = nums.length - 1; // [0,lo) 0s, [lo,mid) 1s, [mid,hi] unread, (hi,n) 2s
while (mid <= hi) {
if (nums[mid] == 0) { int t = nums[lo]; nums[lo++] = nums[mid]; nums[mid++] = t; }
else if (nums[mid] == 1) mid++;
else { int t = nums[hi]; nums[hi--] = nums[mid]; nums[mid] = t; }
}
return nums;
}
}function sortColours(nums) {
let lo = 0, mid = 0, hi = nums.length - 1; // [0,lo) 0s, [lo,mid) 1s, [mid,hi] unread, (hi,n) 2s
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--; }
}
return nums;
}fn solve(nums: &[i64]) -> Vec<i64> {
let mut v = nums.to_vec();
// [0,lo) 0s, [lo,mid) 1s, [mid,hi) unread, [hi,n) 2s; hi is exclusive so it never goes below 0
let (mut lo, mut mid, mut hi) = (0usize, 0usize, v.len());
while mid < hi {
match v[mid] {
0 => { v.swap(lo, mid); lo += 1; mid += 1; }
1 => mid += 1,
_ => { hi -= 1; v.swap(mid, hi); }
}
}
v
}-- One pass that splits the list three ways, kept in order (a stable
-- version of the same partition; lists are not changed in place).
solve :: [Int] -> [Int]
solve xs = zs ++ os ++ ts
where
(zs, os, ts) = foldr put ([], [], []) xs
put 0 (a, b, c) = (0 : a, b, c)
put 1 (a, b, c) = (a, 1 : b, c)
put x (a, b, c) = (a, b, x : c)Variants to try
- Four values instead of three: two passes of a partition, or counting. One-pass partitions get awkward beyond three regions.
- Partition around a pivot value p (less than, equal to, greater than): the same loop with comparisons against p.
Next problems
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem →Write a solution and run it against the real test table.
Keep going
A palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Easy10 minMerge two sorted arrays
The step at the heart of merge sort: one pointer per array, and the smaller front value goes next.
Open the problem → Easy10 minMove the zeros to the end
One pointer reads every element, the other marks where the next non-zero belongs. The order of the non-zero values is kept.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.