Sort Colors (Dutch National Flag) Problem

Sorting an array of red, white, and blue objects—represented by 0, 1, and 2—is a classic real-world task when you need to group items by category in a single pass. In interviews, it tests your array manipulation and two-pointer skills.

Problem Statement

Given an array nums with n elements where each element is 0, 1, or 2, sort the array in-place so that all 0s come first, followed by all 1s, then all 2s. You must solve it in one pass using only constant extra space.

1. Clarify Requirements Before Jumping Into Code

Let me confirm a few details:

• The array must be modified in place; no additional arrays or large buffers allowed.

• Time complexity target is O(n), with a single traversal if possible.

• Space complexity must be O(1), only a few pointers or counters.

• The relative order of equal colors doesn’t matter beyond grouping.

2. Identify the Category of the Question

This is an array partitioning problem that uses the two-pointer (or three-pointer) technique. It’s similar to quicksort’s partition step but specialized for three distinct values. Recognizing “three categories, in place, one pass” points directly to the Dutch National Flag pattern.

3. Consider a Brute-Force Approach to Understand the Problem

The simplest solution is to count occurrences of each color and then overwrite the array:

count0, count1, count2 = counts in nums
overwrite first count0 elements with 0
next count1 elements with 1
last count2 elements with 2

• Time: O(n) to count + O(n) to overwrite = O(n) overall

• Space: O(1) extra for three counters

• Drawback: Two passes over the array; not a true “one-pass” solution

4. Brainstorm More Solutions

A more direct approach is to sort using built-ins, but that’s O(n log n) and violates the one-pass requirement.

Another idea is a two-pass partition: first move all zeros to front using a two-pointer swap, then move all ones to follow. That’s O(n) time but two passes.

Two pointers would work for a solution with just two elements, so what if I build on that?

What if I maintain three pointers, one for each element: low for the next zero spot in the array; mid for the current element; and high for the next two spot in the array. By inspecting nums[mid], we swap with low or high or simply advance mid, achieving a true single-pass in-place partition. That's it!

5. Discuss Trade-Offs Between Your Solutions

Approach	Passes	Time	Space	Pros	Cons
Count & Overwrite	2	O(n)	O(1)	Very simple	Two passes
Two-Pass Partition (0 then1)	2	O(n)	O(1)	In-place, avoids full overwrite	Two passes
Sorting	1–n log n	O(n log n)	O(1)	Single pass with built-in sort	Too slow, not one-pass
Dutch National Flag	1	O(n)	O(1)	True one-pass, in-place	Pointer logic slightly tricky

The Dutch National Flag algorithm is the best fit.

6. Write Pseudocode to Structure Your Thoughts

function sortColors(nums):
    low = 0
    mid = 0
    high = length(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            swap(nums[low], nums[mid])
            low += 1
            mid += 1
        else if nums[mid] == 1:
            mid += 1
        else:  // nums[mid] == 2
            swap(nums[mid], nums[high])
            high -= 1

7. Consider Edge Cases

• Empty array → no action

• All zeros or all twos → pointers handle without swaps

• Single-element array → returns unchanged

• Alternating values, e.g. [2,0,1,2,0,1] → ensures multiple swaps

• Already sorted input → pointers skip quickly

8. Write Full Code Syntax

def sort_colors(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] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

9. Test Your Code

# Test 1: typical mix
arr = [2,0,2,1,1,0]
sort_colors(arr)
assert arr == [0,0,1,1,2,2]

# Test 2: empty
arr = []
sort_colors(arr)
assert arr == []

# Test 3: all zeros
arr = [0,0,0]
sort_colors(arr)
assert arr == [0,0,0]

# Test 4: all twos
arr = [2,2,2]
sort_colors(arr)
assert arr == [2,2,2]

# Test 5: alternating
arr = [1,2,0,1,2,0]
sort_colors(arr)
assert arr == [0,0,1,1,2,2]

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• When in doubt, start with a simpler version of the problem or with a brute force solution, then build on that solution

• Three pointers (low,mid,high) let you handle swaps without extra storage.

• Always update pointers carefully after swaps to avoid skipping elements.

• Visualizing array partitions on paper can prevent pointer errors.

Good luck and happy coding!