The O(n) Club: Sort Colors (LeetCode 75): Dutch Flags, Java, and Pointer-Induced Existential Dread

The O(n) Club: Sort Colors (LeetCode 75): Dutch Flags, Java, and Pointer-Induced Existential Dread

⚡ TL;DR

Need to sort an array of 0s (red), 1s (white), and 2s (blue) in-place, in O(n) time? Put down the counting buckets—Dijkstra’s three-pointer Dutch National Flag makes it a single-pass party. Yes, this is really all you need:

// Java snippet:
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
    if (nums[mid] == 0) swap(nums, low++, mid++);
    else if (nums[mid] == 2) swap(nums, mid, high--);
    else mid++;
}

🧠 How Devs Usually Mess This Up

Most folks try to smuggle in extra arrays (counting sort buckets) or relive the bubble sort years—both get you nowhere fast. Worst case? You still think “if I just do multiple passes, the interviewer won’t notice!” Spoiler: they will, and so will your runtime. Swapping with ‘high’ but moving both pointers is a classic—that leaves unsorted misfits in your array, like socks after laundry day.

🔍 What’s Actually Going On

Imagine you’re a warehouse robot with one tray and an over-caffeinated manager yelling: “Red on the left! White in the middle! Blue on the right! No re-runs!” You set up three pointers: low (left boundary for reds), mid (scanning inspector), and high (right boundary for blues). As you inspect each marble:

• 0: Swap with low, then move both low and mid over (red zone expands—parade time).
• 1: Glance, shrug, move mid (white is chill).
• 2: Panic swap with high, shrink high; don’t move mid yet (you just brought in a stray, who still needs a check).

Repeat until mid overtakes high. Congrats—you’ve built the Dutch flag out of Java variables and caffeine. Bonus thought: the single-pass makes this pointer dance better than any sorting method your CompSci textbook still ships out.

🛠️ PseudoCode

• Create low=0, mid=0, high=nums.length-1.
• While mid <= high:
  • If nums[mid]==0: swap with low, low++, mid++;
  • Else if nums[mid]==2: swap with high, high–;
  • Else (nums[mid]==1): mid++;
• Done (as in, you can now smile at the interviewer and try not to spill coffee).

// Swap helper for Java
void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

💻 The Code

public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums, low, mid);
            low++;
            mid++;
        } else if (nums[mid] == 2) {
            swap(nums, mid, high);
            high--;
        } else { // nums[mid] == 1
            mid++;
        }
    }
}
 private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Do NOT advance mid after swapping with high. That new element could be a 0, 1, or 2—respect the chaos!
• Edge cases? Sure: empty array, all-same-color, or just two colors. Solution eats them for breakfast.
• In-place, O(1) space. If you reach for a new array, drop and give me 20 (push-ups or commits—your call).
• One pass. One. (O(n)). If you loop more, Edsger Dijkstra issues a silent, dignified sigh.

🧠 Interviewer Brain-Tattoo

“If three pointers can keep the Netherlands sorted, they can tame your array too.” Java, flags, caffeine, and zero buckets: that’s progress.