Given an array containing only the values 0, 1 and 2, sort it in place in a single pass without using a separate counting or sorting step.
Video coming soon
We're producing a video walkthrough — check back soon.
Given an array containing only the values 0, 1 and 2, sort it in place in a single pass without using a separate counting or sorting step.
The canonical three-way partition problem — it extends Segregate 0s and 1s' two boundary pointers with a third, 'current element' pointer, which is the real cognitive jump most people trip on first.
Whenever an array holds exactly three distinct values and needs sorting in one pass without extra space, that's the Dutch National Flag signal: track a low boundary, a high boundary, and a current scanning pointer between them.
Maintain three pointers: low (everything before it is a confirmed 0), high (everything after it is a confirmed 2), and mid (the element currently being classified), with mid starting at 0 and high starting at the last index. While mid <= high: if nums[mid] is 0, swap it with nums[low], then advance both low and mid, since the value now at mid (swapped from low) is already known to be 0 or 1 and safe to move past. If nums[mid] is 1, it's already in its correct region, so just advance mid. If nums[mid] is 2, swap it with nums[high] and decrement high without advancing mid — the value swapped in from high hasn't been classified yet and needs to be examined next.
class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp;
high--;
}
}
}
}