Dutch National Flag
The Dutch National Flag problem (also known as 3-way partitioning) sorts an array containing only three distinct values. Named after the Dutch flag with three stripes, it groups identical elements together.
Classic problem: sort an array of 0s, 1s, and 2s without using extra space and in a single pass.
The algorithm uses three pointers:
low– boundary for 0s.mid– current element.high– boundary for 2s.
Java implementation:
public static void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
switch (nums[mid]) {
case 0:
swap(nums, low, mid);
low++; mid++;
break;
case 1:
mid++;
break;
case 2:
swap(nums, mid, high);
high--;
break;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
This is a special case of 3-way partitioning. The same idea can be extended to partition arrays based on a pivot (like in Quick Sort).
Two Minute Drill
- Dutch National Flag algorithm sorts an array of 0s, 1s, 2s in O(n) time and O(1) space.
- Uses three pointers: low, mid, high.
- 0s go to left, 2s to right, 1s stay in middle.
- Common interview problem; also called sort colors".
Need more clarification?
Drop us an email at career@quipoinfotech.com