Sorting usually means:
O(n log n)
Extra space
But what if the array contains only 3 distinct values?
You can sort it in:
O(n) time
O(1) space
Single pass
That’s the Dutch National Flag Algorithm.
Core Idea
Use three pointers:
low → boundary for 0s
mid → current element
high → boundary for 2s
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; } }
Enter fullscreen mode
Exit fullscreen mode
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
How It Works
At each step:
If 0 → move to left
If 1 → keep in middle
If 2 → move to right
All done in one traversal
The Real Insight
Instead of sorting, we partition the array
This is similar to Quick Sort partitioning.
Key Insights
Three-pointer technique
In-place…