#75
Sort Colors
Medium Dutch National Flag
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array contains only 0, 1 and 2. Sort it in place in one pass without using a library sort.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sort 0s, 1s and 2s in one pass, in place.
Why this works: three zones: [0..low) are 0s, [low..mid) are 1s, (high..end] are 2s. Look at nums[mid] and send it to the right zone.
Example: [2, 0, 2, 1, 1, 0]
mid=0 is 2 → swap with high → [0, 0, 2, 1, 1, 2]0 → low, 0 → low, 2 → swap with high → [0, 0, 1, 1, 2, 2]1, 1 → mid moves → done
✦Hints open one at a time
Keep three regions: 0s at the front, 2s at the back, 1s in the middle.
Use pointers low, mid, high. Look at nums[mid].
After swapping a 2 to the back, don't move mid — the swapped-in value hasn't been checked yet.
↗Approach
Dijkstra's three-way partition. 0 → swap with low, move low and mid. 1 → move mid. 2 → swap with high, move high only. Stop when mid passes high.
</>Solution (Java)
class Solution {
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: new value unchecked
}
}
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
}!Common mistake
Advancing mid after swapping with high, which skips an unchecked element.
Complexity
- Time: O(n), one pass.
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon