The problem is pretty simple. You are given an array with only three distinct values - 0, 1, 2, and you want them to be sorted in-place. Surely you can utilzie any typical in-place sorting algorithms like insertion sort or quick sort- but they cannot go better than O(nlogn) time complexity. As we have only three distinct values across the entire array, can we do better?
That’s where the Dutch National Flag Algorithm (DNF) comes in. DNF can solve the problem within linear time using only constant extra space. One-pass is all you need! As DNF sorts the array in just O(n) time, you should already know that it is not one of the comparision-based sorting algorithms which take at least nlogn time.
In DNF, we divide the entire array into three seperate regions or zones. We mark the boundary of the zones with three pointers- i, k and j.
So we keep the following invariants:
[0..i] → all 0s (red)
[i+1..k-1] → all 1s (white)
[k..j-1] → unknown (to process)
[j..end] → all 2s (blue)
i is initialized at one index previous to the beginning of the array (at -1) and j is initialized at one index next to the end of the array (at array.size()). And the k pointer is initialized at 0, at the beginning of the array. k index dentoes the current array item being inspected.
The idea is simple. We scan kth position from left toward right until it meets j. As we proceed, we will send the 0s to the left at their zone and the 2s to the right at their zone. And this will automatically place the 1s appropriately in their own zone as well. Details are as stated below:
If we encounter a 2 at kth index, - First we decrement j to expand the 2s zone. (j=j-1) - And then, swap the item at kth position with the item at the jth position. - But we don’t increment k because the swapped-in item from the current jth index can be anything- 0, 1 or 2, so it must be checked before we proceed k.
If it’s a 0, - First we increment i to expand the 0s zone. (i=i+1) - And then, we swap the item at kth position with the item at ith position. - Then we are good to increment k as well. Because if there’s a 1s zone (i < k after swapping), the swapped-in value at k is a 1, correctly placed for the 1s zone, so we increment k. If i == k after swapping (meaning no 1s zone yet), the swap changes nothing, but k is now in the 0s zone, and incrementing k safely processes the next element. [For the later case, take a quick example: 0, 1, 2]. Thus, it is safe to increment k in either cases.
If it’s a 1, - Just increment k. As we are basicaly putting 0s and 2s at their appropriate positons, so the 1s will be where it shouold actually be.
This guarantees each element is processed at most once, so it’s linear time, and we only use three integer pointers, so constant extra space.
Here goes the AC code with comments added.
class Solution {
public:
void sortColors(vector<int>& nums) {
// i will track the last position of 0 (reds), initialized to -1 (none yet)
int i = -1;
// j will track the first position of 2 (blues) from the end, initialized to nums.size()
int j = nums.size();
// k is our current index, we scan from left to right
int k = 0;
// Process elements until k meets j
while (k < j) {
if (nums[k] == 2) {
// Found a blue (2). Decrement j to expand the blue-zone at the right,
// then swap this 2 into that zone. Do NOT increment k here,
// because the element we swapped in might be 0, 1, or 2 and needs checking.
j--;
swap(nums[k], nums[j]);
}
else if (nums[k] == 0) {
// Found a red (0). Increment i to expand the red-zone at the left,
// then swap this 0 into that zone. We can safely increment k,
// since everything before i is already processed and correct.
i++;
swap(nums[k], nums[i]);
k++;
}
else {
// nums[k] == 1, i.e. white. Just leave it where it is,
// expand the white-zone by moving k forward.
k++;
}
}
}
};