The flag of the Netherlands consists of three colors: red, white, and blue. Given balls of these three colors arranged randomly in a line (it does not matter how many balls there are), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.
If we use normal sorting algorithms to solve this problem, the best average time complexity is O(nlog(n)). Since this is a problem with limited situations, can we use its feature to make the algorithms to do better?
Of course we can. Since there are only 3 types of element, the idea is to use a two pointer solution. We define two poninter low and high and we iterate the array. If current element should be in the first part, we make it swap with the low pointer element, then move the low pointer forward. If the current element should be in the last part, we make it swap with the high pointer element, and move the high pointer backward. In this way, after the iteration, we should make the low and high elements in right order, and the middle elements should in its order naturally.
Let's use this algorithm to solve the leetcode Sort Colors problem.
function sortColors(nums: number[]): void {
let low = 0;
let high = nums.length - 1;
let i = 0;
while (i <= high) {
if (nums[i] === 0) {
[nums[i], nums[low]] = [nums[low], nums[i]];
low += 1;
i += 1;
} else if (nums[i] === 2) {
[nums[i], nums[high]] = [nums[high], nums[i]];
high -= 1;
// here, no i += 1
} else {
i += 1;
}
}
};
One thing needed to be noted is that, since we iterate the array from left to right, so when we swap current element with the high pointer element, we should check the element again.