Sort Colors

The Goal

We need to sort an array containing only 0s, 1s, and 2s. The catch is that we must do this in-place (without creating a new array) and ideally in one pass (O(n) time).

• 0: Represents Red (should be at the beginning)
• 1: Represents White (should be in the middle)
• 2: Represents Blue (should be at the end)

Input/Output Examples

• Input: nums = [2, 0, 2, 1, 1, 0]

• Output: [0, 0, 1, 1, 2, 2]

• Input: nums = [2, 0, 1]

• Output: [0, 1, 2]

Constraints

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Note: A simple solution would be to count the number of 0s, 1s, and 2s, and then overwrite the array. However, the "Dutch National Flag" algorithm allows us to do this in a single pass with constant space.

The Dutch National Flag Algorithm

This problem is a classic variation of the Dutch National Flag problem proposed by Edsger Dijkstra. We use three pointers to partition the array into three sections:

1. low: The boundary for 0s (Red). Everything before low is 0.
2. high: The boundary for 2s (Blue). Everything after high is 2.
3. mid: The current element iterator. Everything between low and mid is 1 (White).

The Logic

We iterate with the mid pointer and check nums[mid]:

1. If nums[mid] == 0:
   • This belongs in the "0 zone" (at the start).
   • Swap nums[mid] with nums[low].
   • Increment both low and mid.
2. If nums[mid] == 1:
   • This belongs in the middle. It's already in the right relative place.
   • Just increment mid.
3. If nums[mid] == 2:
   • This belongs in the "2 zone" (at the end).
   • Swap nums[mid] with nums[high].
   • Decrement high.
   • Crucial: Do NOT increment mid yet! The element we just swapped from high to mid hasn't been checked. We need to process it in the next iteration.

Visualizing the Zones

[0, 0, ... 0    1, 1, ... 1    ?, ?, ... ?    2, 2, ... 2]
^              ^              ^              ^
0             low            mid            high

Watch low, mid and high partition the array: everything before low is 0, everything after high is 2, and mid decides where the next value goes.

Let's trace the algorithm with nums = [2, 0, 2, 1, 1, 0].

Common Pitfalls

1. Incrementing mid after swapping with high: This is the most common bug. When you swap with high, the new element at mid could be a 0 or a 2. You must check it again.
2. Off-by-one errors: Ensure logic handles the last element properly (use mid <= high).

Edge Cases

• No 0s, 1s, or 2s: E.g., [1, 1, 1] or [2, 2, 2]. The algorithm still works.
• Already Sorted: The pointers will just verify the order.
• Reverse Sorted: [2, 2, 1, 1, 0, 0]. Just requires more swaps.

Implementations in JavaScript, TypeScript, Python, Java, C and C++.