How do you sort an array of 0s, 1s and 2s in a single pass?
Use the Dutch national flag method with three pointers: low for the next 0 position, high for the next 2 position, and mid scanning. Swap 0s to the front and 2s to the back; leave 1s in the middle.
Explain it simply
Imagine arranging students in a school assembly by house colour: red, white, blue. You do not need a full sort. You only need three zones: red at the front, blue at the back, and white in between.
Walk through with mid. If you see red (0), swap it with the front boundary and advance both. If you see blue (2), swap it with the back boundary and shrink the back, but do not advance mid yet because the swapped-in value is unchecked. White (1) just moves on.
Example
function sortColors(nums) {
let low = 0;
let mid = 0;
let 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 {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
return nums;
}
console.log(sortColors([2, 0, 2, 1, 1, 0])); // Output: [0,0,1,1,2,2]Complexity
Time O(n), space O(1).
What to say in the interview
"I keep three zones with pointers low, mid and high. A 0 swaps with low, a 2 swaps with high, and a 1 stays. After swapping with high I do not advance mid, because the value that arrived has not been inspected. It is one pass, O(n) time and O(1) space."
Common mistakes
- Advancing mid after swapping with high, which skips an unchecked element.
- Using the library sort and ignoring that the question asks for a single pass.