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.…