Sort Colors (Dutch National Flag) Problem
- mosesg1123
- 4 days ago
- 3 min read
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!
Comments