What is the Dutch National Flag Problem?
Learn the three-pointer approach to the Dutch National Flag problem for sorting three-value arrays in one pass.
Expected Interview Answer
The Dutch National Flag problem asks you to sort an array containing only three distinct values (classically 0s, 1s, and 2s) into three contiguous groups in a single pass, and it is solved with three pointers — low, mid, and high — that partition the array in O(n) time and O(1) space without extra sorting.
The array is conceptually divided into four regions as the mid pointer scans left to right: values below low are confirmed 0s, values between low and mid are confirmed 1s, values between mid and high are unprocessed, and values above high are confirmed 2s. At each step you look at nums[mid]: if it is 0, swap it with nums[low], advance both low and mid; if it is 1, just advance mid since it is already in the right region; if it is 2, swap it with nums[high] and decrement high without advancing mid, because the swapped-in value still needs to be examined. The loop continues until mid crosses high, at which point every element has been classified into its correct region. This is a specialized three-way partition, a generalization of the two-way partition used in quicksort, and the same pattern applies to any problem requiring in-place grouping of three known categories.
- O(n) time, single pass
- O(1) extra space, sorts in place
- Avoids a full O(n log n) comparison sort
- Generalizes the quicksort partition to three groups
AI Mentor Explanation
A groundskeeper needs to sort scattered training cones by color — red, yellow, and green — into three contiguous zones on the pitch in one walk. They keep three markers: a boundary for confirmed reds on the left, a boundary for confirmed greens on the right, and a walking point in between that inspects each cone. A red cone gets swapped to the left boundary and both the left boundary and walking point move forward; a yellow cone is already in the middle zone so only the walking point advances; a green cone gets swapped to the right boundary, which moves inward, but the walking point stays put to inspect whatever just got swapped in. By the time the walking point meets the right boundary, every cone sits in its correct color zone without ever sorting the whole pitch.
Step-by-Step Explanation
Step 1
Initialize three pointers
low = 0, mid = 0, high = len(nums) - 1.
Step 2
Handle a 0 at mid
Swap nums[low] and nums[mid], then increment both low and mid.
Step 3
Handle a 1 at mid
Leave it in place and just increment mid.
Step 4
Handle a 2 at mid
Swap nums[mid] and nums[high], decrement high, but keep mid unchanged to re-check the swapped-in value.
What Interviewer Expects
- State O(n) time, O(1) space, single-pass, in-place solution
- Explain the four-region invariant (low/mid/high) precisely
- Explain why mid does NOT advance after a swap with high
- Connect this to the quicksort three-way partition (Lomuto/Dutch flag variant)
Common Mistakes
- Advancing mid after swapping with high, which skips checking the swapped-in value
- Using a full comparison sort (O(n log n)) instead of the O(n) three-pointer partition
- Forgetting the loop condition should be mid <= high, not mid < len(nums)
- Confusing this with a simple two-pointer partition meant for only two categories
Best Answer (HR Friendly)
“The Dutch National Flag problem is about sorting an array that only has three distinct values into three groups in a single pass. I use three pointers — one tracking where the low group ends, one scanning through the array, and one tracking where the high group starts — swapping elements into place as I go, so the whole array is grouped correctly without a full sort.”
Code Example
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
return nums
print(sort_colors([2, 0, 2, 1, 1, 0])) # [0, 0, 1, 1, 2, 2]Follow-up Questions
- How would you generalize this partition scheme to k distinct categories?
- How does this relate to the three-way partitioning used in some quicksort variants?
- What would break if you advanced mid after a swap with high?
- How would you solve this if the values were not known in advance to be only three categories?
MCQ Practice
1. What is the time complexity of the Dutch National Flag algorithm?
The three-pointer partition classifies every element in a single pass, giving O(n) time.
2. After swapping nums[mid] with nums[high] because nums[mid] was 2, what should happen to mid?
The swapped-in value at mid has not been examined yet, so mid must stay to re-check it.
3. What does the region between low and mid represent during the algorithm?
Elements between low and mid have already been classified as the middle value (1) and are in their final position.
Flash Cards
What does the Dutch National Flag problem sort? — An array of three distinct values into three contiguous groups.
What is the time and space complexity of the three-pointer solution? — O(n) time, O(1) space.
How many pointers does the classic solution use? — Three: low, mid, and high.
Why does mid not advance after swapping with high? — Because the newly swapped-in value at mid still needs to be classified.