Algorithm

Sort Colors (Dutch National Flag)

Two Pointer Pattern

Sort Colors (Dutch National Flag)

Given an array nums with n objects colored red, white, or blue (represented as 0, 1, or 2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red (0), white (1), and blue (2). You must solve this without using the library's sort function.

CONSTRAINTS
  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2
  • Come up with a one-pass algorithm using only constant extra space
EXAMPLE 1
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
All 0s come first, then the 1s, then the 2s.
EXAMPLE 2
Input: nums = [2,0,1]
Output: [0,1,2]
One of each, arranged into the required 0-then-1-then-2 order.
EXAMPLE 3
Input: nums = [1,1,1]
Output: [1,1,1]
All values are the same, so nothing needs to move.
Can the input contain values other than 0, 1, and 2?
No — only those three. That is exactly what lets us skip a general sort.
Is a two-pass counting solution acceptable?
It is correct and O(N), but the intended answer is a single pass with O(1) extra space.
Does the array get sorted in place, or should I return a new one?
In place. The original array is rearranged and nothing is returned.

Sorting an array with only three distinct values (0, 1, and 2) is a specialized challenge. While you could use a standard sorting algorithm, the fixed set of values allows us to be much more efficient. The goal is to group all identical numbers together in the order 0, 1, and 2 without using extra space.

One straightforward way to solve this is the Two-Pass Counting approach. In the first pass, we simply count how many zeros, ones, and twos exist in the array. In the second pass, we overwrite the original array with that many zeros, then that many ones, and finally the remaining twos.

python
# Two-Pass Counting (O(N) Time, O(1) Space)
counts = [0, 0, 0]
for x in nums:
    counts[x] += 1

idx = 0
for color in range(3):
    for _ in range(counts[color]):
        nums[idx] = color
        idx += 1

While efficient, this requires two full passes. To solve the problem in a Single Pass, we use the Dutch National Flag algorithm. We imagine the array as three distinct regions: the "Red" zone (0s) at the front, the "Blue" zone (2s) at the back, and the "White" zone (1s) in the middle. We use three pointers to maintain these boundaries:
- low: Everything to the left of this pointer is a confirmed 0.
- high: Everything to the right of this pointer is a confirmed 2.
- mid: The explorer that inspects every element from left to right.

The strategy works as follows:
- If we see a 0: Swap it with the low pointer and move both low and mid forward.
- If we see a 2: Swap it with the high pointer and move high backward. We do not move mid yet because we need to inspect the value that just arrived from the back.
- If we see a 1: Just move mid forward.

python
# One-Pass DNF (O(N) Time, O(1) Space)
low, mid = 0, 0
high = 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] == 2:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
    else: # nums[mid] == 1
        mid += 1
Worked Example:[2, 0, 2, 1, 1, 0]
0
2
low/mid
1
0
2
2
3
1
4
1
5
0
high
We start with low and mid at index 0, and high at index 5. mid sees a 2, so we swap it with high.
0
0
low/mid
1
0
2
2
3
1
4
1
high
5
2
After swapping mid (2) with high (0), high shrinks to index 4. mid now sees a 0, so we swap with low.
0
0
1
0
low/mid
2
2
3
1
4
1
high
5
2
We swap mid (0) with low (0). Both low and mid advance to index 1. mid sees another 0, so we swap again.
0
0
1
0
2
2
lowmid
3
1
4
1
high
5
2
We swap mid (0) with low (0). low and mid advance to index 2. mid sees 2, so we swap with high (index 4).
0
0
1
0
2
1
lowmid
3
1
high
4
2
5
2
After swapping mid (2) with high (1), high shrinks to 3. mid now sees a 1, so we simply advance mid.
0
0
1
0
2
1
low
3
1
highmid
4
2
5
2
mid advances to index 3 and sees a 1. Since mid now exceeds high, the sorting process is complete.
Interactive Strategy Visualization

Dutch National Flag

3-Way Partitioning with Pointers

LOW
MID
2
0
0
1
2
2
1
3
1
4
HIGH
0
5
Initializing pointers: low and mid at 0, high at the end.

Key Insight

We maintain three zones: [0, low-1] for 0s, [low, mid-1] for 1s, and [high+1, n-1] for 2s. mid explores the unknown.

One Pass Strategy

If mid finds a 0, swap with low and advance both. If 1, just advance mid. If 2, swap with high and shrink high only.

O(N log N) Comparison Sort
→
O(N) Time · O(1) Space Two-Pass Count
→
O(N) Time · O(1) Space One-Pass Partition