Introduction

The Sort Colors problem (LeetCode #75) presents us with a unique constraint: we are given an array containing objects colored red, white, and blue, represented by the integers 0, 1, and 2]. We need to sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue (all 0s, then all 1s, then all 2`s).

The real catch? You are not allowed to use the library's built-in sort function.

While a naive approach like counting the occurrences of each number and overwriting the array works (a two-pass solution), there is a legendary linear, single-pass approach known as the Dutch National Flag Algorithm.

---

The Naive Approach (Counting)

The simplest workaround is to loop through the array once and count how many 0s, 1s, and 2s there are. Then, loop through the array a second time and overwrite it with the correct number of 0s, followed by 1s, and finally 2s.

Why it's not the best

While this approach runs in O(N) time, it requires two full passes over the array. Interviewers will almost always challenge you to do it in a single pass with constant auxiliary space.

---

The Elite Approach: Dutch National Flag Algorithm

Invented by computer scientist Edsger Dijkstra, this algorithm uses three pointers to slice our array into four distinct logical zones as we iterate through it.

The Array Partition Invariant:

• [0 ... low-1] -> Strictly 0s (Red zone)
• [low ... mid-1] -> Strictly 1s (White zone)
• [mid ... high] -> Unexamined elements (Unknown zone)
• [high+1 ... end] -> Strictly 2s (Blue zone)

Our mid pointer acts as the active explorer, scanning elements from left to right while low and high hold the boundaries.

---

How the Pointers Move

We initialize low = 0, mid = 0, and high = nums.length - 1. We run our loop as long as mid <= high.

Case 1: We find a Red color (nums[mid] == 0)

This belongs in the lower boundary. We swap nums[mid] with nums[low]. Because we know a 1 was shifted to the mid position, we can safely advance both pointers:

• low++
• mid++

Case 2: We find a Blue color (nums[mid] == 2)

This belongs in the upper boundary. We swap nums[mid] with nums[high]. Since we have no idea what value was just swapped back into the mid position from the end of the array, we do not advance mid. We only shrink our upper boundary:

• high--

Case 3: We find a White color (nums[mid] == 1)

This is already in its correct relative position (the middle zone). No swapping is needed; we simply move our explorer forward:

• mid++

---

The Java Solution

Here is the clean implementation of the single-pass partition strategy:

java
Copy
class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap current element with the low boundary element
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 2) {
                // Swap current element with the high boundary element
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
                // Note: mid is NOT incremented here because the new elements
                // brought from high needs to be evaluated in the next iteration!
            } else {
                // If it's a 1, it's already in the middle zone
                mid++;
            }
        }
    }
}

---

Complexity Analysis

This approach optimizes our processing layout to its maximum limits:

• Time Complexity: O(N) — We scan the elements of the array at most one time. Every single step either advances our explorer (mid) or shrinks the unseen range (high).
• Space Complexity: O(1) — The sorting is done entirely in-place by swapping variables. No auxiliary tracking maps or arrays are allocated.

Final Thoughts

The Sort Colors problem is a fantastic illustration of pointer tracking. By maintaining clear boundary invariants (low for 0s, high for 2s), we can sort a three-valued array cleanly in a single sweep. It's a fundamental trick to keep tucked away for any partitioning or partitioning-adjacent interview question!