Sort Colors LeetCode 75 Guide

LeetCode 75 — Sort Colors — presents an array nums containing only the values 0, 1, and 2, representing the colors red, white, and blue respectively. The task is to sort the array in-place so that all 0s appear first, all 1s appear second, and all 2s appear last — matching the order of the Dutch national flag. You must not use any library sorting function.

The problem has a straightforward two-pass solution using counting sort: count the occurrences of 0, 1, and 2 in the first pass, then overwrite the array in the second pass using those counts. This runs in O(n) time and O(1) space and is perfectly correct. However, the follow-up challenge asks whether you can solve the problem in a single pass — and that is where the Dutch National Flag algorithm comes in.

This problem is a foundational array partitioning exercise. It tests your ability to maintain invariants while manipulating pointer positions and performing in-place swaps. The same three-way partitioning technique is the basis for the three-way quicksort partition, the Dutch National Flag variant of quicksort for arrays with many duplicate keys, and related problems like kth largest element.

The two-pass counting sort solution is simple and correct: iterate the array once to count 0s, 1s, and 2s; then overwrite the array filling count0 zeros, then count1 ones, then count2 twos. This is O(n) time and O(1) space and solves the problem completely. For most interview contexts, presenting this solution first and then improving to one-pass is the ideal approach.

The limitation of counting sort is that it requires two passes over the data — one to gather counts and one to rewrite values. The follow-up challenge specifically asks whether you can sort the array in a single traversal without any pre-counting phase. The Dutch National Flag algorithm achieves this by maintaining three running pointers that collectively enforce a four-region invariant as they sweep through the array once.

Understanding why one-pass matters in practice: in streaming scenarios where data arrives element by element and you cannot buffer it for a second scan, one-pass algorithms are strictly necessary. In interview settings, the one-pass constraint demonstrates mastery of pointer manipulation and loop invariant reasoning — skills that transfer directly to partition-based algorithms in quicksort and related problems.

The Dutch National Flag algorithm uses three integer pointers: low, mid, and high. Initialize low = 0, mid = 0, and high = n - 1 where n is the length of the array. The algorithm proceeds while mid <= high, performing swaps and pointer moves based on the value at nums[mid].

The invariant maintained throughout the algorithm divides the array into four regions at all times. Elements in indices [0, low-1] are guaranteed to be 0s. Elements in indices [low, mid-1] are guaranteed to be 1s. Elements in indices [mid, high] are the unprocessed region whose final positions are not yet determined. Elements in indices [high+1, n-1] are guaranteed to be 2s. When mid passes high, the unprocessed region is empty and the array is fully sorted.

This four-region invariant is the core of the algorithm. Every swap and pointer movement is chosen specifically to preserve or advance the invariant. When mid crosses high, all four regions are non-empty only for their correct values — the sort is complete without any second pass over the data.

The algorithm processes nums[mid] on each iteration with three cases. Case 1: if nums[mid] == 0, swap nums[mid] with nums[low], then increment both low and mid. The 0 is now in its correct region, and the element that was at low (which we know is a 1 since it was in the [low, mid-1] region) has been moved to mid and is still correctly classified, so mid can safely advance.

Case 2: if nums[mid] == 1, simply increment mid without any swap. The element is already in the correct 1s region between low and mid, so advancing mid extends the sorted 1s region by one position with no work required.

Case 3: if nums[mid] == 2, swap nums[mid] with nums[high], then decrement high only — do not increment mid. The 2 is now in its correct region at the high end. However, the element that was at high and is now at mid is unknown — it could be a 0, 1, or 2 — so mid must stay in place to classify that newly revealed element on the next iteration.

Trace the algorithm on nums = [2, 0, 2, 1, 1, 0]. Initial state: low = 0, mid = 0, high = 5. nums[mid] = nums[0] = 2, so swap with high: swap(0, 5) → [0, 0, 2, 1, 1, 2], then high = 4. Now mid = 0, low = 0, high = 4. nums[mid] = 0, so swap with low: swap(0, 0) → [0, 0, 2, 1, 1, 2] (no change), then low = 1, mid = 1.

Continue: mid = 1, low = 1, high = 4. nums[mid] = 0, so swap with low: swap(1, 1) → [0, 0, 2, 1, 1, 2] (no change), low = 2, mid = 2. Now mid = 2, low = 2, high = 4. nums[mid] = 2, so swap with high: swap(2, 4) → [0, 0, 1, 1, 2, 2], then high = 3. mid = 2, low = 2, high = 3.

Continue: nums[mid] = nums[2] = 1, so just mid = 3. Now mid = 3, low = 2, high = 3. nums[mid] = 1, so just mid = 4. Now mid = 4 > high = 3, loop ends. Final array: [0, 0, 1, 1, 2, 2]. The algorithm performed 5 iterations and 2 actual swaps to fully sort the array.

Python solution: def sortColors(nums): low, mid, high = 0, 0, len(nums) - 1; while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low]; low += 1; mid += 1; elif nums[mid] == 1: mid += 1; else: nums[mid], nums[high] = nums[high], nums[mid]; high -= 1. This is the complete solution — roughly 10 lines including the function signature. Time complexity O(n), space O(1).

Java solution: public void sortColors(int[] nums) { int low = 0, mid = 0, high = nums.length - 1; while (mid <= high) { if (nums[mid] == 0) { int tmp = nums[low]; nums[low++] = nums[mid]; nums[mid++] = tmp; } else if (nums[mid] == 1) { mid++; } else { int tmp = nums[high]; nums[high--] = nums[mid]; nums[mid] = tmp; } } }. Both solutions are concise, in-place, and handle edge cases (all same color, already sorted, reverse sorted) correctly without modification.

The algorithm always terminates because on every iteration, either mid increases (Cases 1 and 2) or high decreases (Case 3), so the size of the unprocessed region [mid, high] strictly decreases by 1 on each step. The total number of iterations is at most n, confirming O(n) time complexity. The number of swaps is at most n - 1, which is also optimal for an in-place sort of this problem.

The Dutch National Flag three-way partition is the basis for three-way quicksort, which outperforms standard two-way quicksort on arrays with many duplicate keys. Instead of partitioning into two regions (less than pivot, greater than pivot), three-way quicksort partitions into three: less than, equal to, and greater than. For arrays where all elements are equal, three-way quicksort completes in O(n) while standard quicksort degrades to O(n²).

The quickselect algorithm for Kth Largest Element in an Array (LeetCode 215) uses a similar partition step. Each call to partition places the pivot in its correct sorted position and tells you which side the kth element is on, reducing the search space by a constant fraction on average. Understanding the Sort Colors partition invariant directly accelerates your intuition for quickselect's correctness argument.

Other problems in the partitioning family include: Next Permutation (LeetCode 31), which uses a two-phase scan to find the next lexicographic arrangement; Container With Most Water (LeetCode 11), which uses a two-pointer squeeze from both ends; and Partition List (LeetCode 86), which rearranges a linked list around a pivot value. All of these share the core insight that maintaining pointer invariants through a single linear scan is more powerful than naive two-pass approaches.