Dutch National Flag — Problem Statement & Solution Guide
Problem Description
You are given an array of integers that contains only the values 0, 1, and 2. Your task is to reorder the array so that all 0s appear first, followed by all 1s, and finally all 2s. The reordering must be performed in a single left‑to‑right pass through the array, using only a constant amount of additional memory. The relative order of elements within each group does not matter.
Input: A single line containing the array elements separated by spaces.
Output: The array after it has been rearranged into the required order, printed on one line with elements separated by spaces.
The algorithm should run in linear time, O(n), and use O(1) extra space, making it suitable for large input sizes.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Dutch National Flag"
WHY DOES IT MATTER?
The three‑pointer pattern is essential because it transforms a problem that could naively require sorting or multiple passes into a linear, in‑place solution. It demonstrates mastery of pointer manipulation, loop invariants, and space optimization—skills highly valued in system design and performance‑critical code.
OPTIMIZATION CHALLENGE
The key insight is that you can decide the destination of each element on the fly using only its value, without needing to count or sort. By swapping 0s to the front and 2s to the back, you shrink the unsorted region from both ends, guaranteeing that each element is examined at most twice.
REAL-WORLD CONNECTION
Think of a warehouse with three types of boxes that must be arranged on a conveyor belt: the algorithm is like a worker who, while scanning the belt, swaps boxes into the correct zone without stopping the belt. In distributed systems, it’s analogous to a single pass over a data stream that partitions records into buckets for downstream processing.
When implementing, remember to decrement the high pointer after swapping a 2 and *do not* increment mid in that iteration. This subtle detail ensures that the element swapped from the high end is re‑evaluated, preventing missed 0s or 1s.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Dutch National Flag problem is a classic example of in‑place partitioning that can be solved in a single linear scan. A naive approach would sort the array using a comparison sort (O(n log n)) or count the occurrences of 0, 1, and 2 and then rewrite the array (O(n) time but requires an extra pass or additional memory). Both fail to meet the strict requirement of a single left‑to‑right pass with constant extra space. The optimal solution, introduced by Edsger W. Dijkstra, uses three pointers—low, mid, and high—to maintain the boundaries of the three partitions. As mid traverses the array, elements are swapped into place: 0s go to the front, 2s to the back, and 1s stay in the middle. This guarantees O(n) time, O(1) space, and a single pass.
The underlying algorithmic theory is that of *three‑way partitioning*, a generalization of the two‑pointer technique used in quicksort’s partition step. By maintaining explicit boundaries for each value, we avoid unnecessary comparisons and swaps. The algorithm’s correctness follows from invariant maintenance: at any point, indices < low contain 0s, indices > high contain 2s, and mid points to the current element under inspection. When mid encounters a 0, swapping with low expands the 0 region; when it encounters a 2, swapping with high shrinks the 2 region and forces a re‑evaluation of the swapped element. This elegant loop invariant ensures linear progress and constant space usage.
Interview Questions on This Problem
Q1How would you modify the Dutch National Flag algorithm if the array could contain any three distinct values, not just 0, 1, and 2?
The algorithm remains the same: identify the three distinct values, assign them to low, mid, and high partitions, and perform swaps based on the current element’s value. The key is to map each value to a partition index and use the same three‑pointer logic. If the values are not known in advance, you can first determine the unique values by scanning once, then apply the partitioning. This preserves O(n) time and O(1) space.
Q2In a distributed system, you need to sort a stream of 0s, 1s, and 2s across multiple nodes. How would you adapt the Dutch National Flag approach?
Each node can locally partition its chunk using the three‑pointer method, producing counts of 0s, 1s, and 2s. Then a reduce phase aggregates these counts and redistributes the elements so that all 0s, 1s, and 2s are contiguous across nodes. This two‑phase approach keeps local processing O(n) and communication minimal, leveraging the same partitioning logic at scale.
Q3What interview pitfalls should you watch for when explaining the Dutch National Flag solution to a hiring manager?
Common pitfalls include: (1) claiming the algorithm uses extra memory for the three pointers; (2) confusing the swap logic for 0s and 2s; and (3) overlooking the need to decrement high after swapping a 2, which forces re‑evaluation of the swapped element. Clarify that the three indices are stored in variables, not arrays, and that the algorithm runs in a single pass with constant space.
Examples
Input
2 0 2 1 1 0
Output
undefined
Explanation: Start with three pointers: low=0, mid=0, high=5. Process mid=0 (value 2): swap with high, high becomes 4. Process mid=0 again (value 0): swap with low, low=1, mid=1. mid=1 (value 0): swap with low, low=2, mid=2. mid=2 (value 1): mid++ to 3. mid=3 (value 1): mid++ to 4. mid=4 > high, stop. Result: 0 0 1 1 2 2.
Input
0 0 1 1 2 2
Output
undefined
Explanation: All elements are already in the correct order. The algorithm still scans the array once, performing no swaps, and the final array remains unchanged.
Input
1 0 2 1 0 2 1
Output
undefined
Explanation: low=0, mid=0, high=6. mid=0 (1): mid++ to 1. mid=1 (0): swap with low, low=1, mid=2. mid=2 (2): swap with high, high=5. mid=2 (2): swap with high, high=4. mid=2 (1): mid++ to 3. mid=3 (1): mid++ to 4. mid=4 (0): swap with low, low=2, mid=5. mid=5 > high, stop. Result: 0 0 1 1 1 2 2.
Input
2 2 2 1 1 0 0 0
Output
undefined
Explanation: The algorithm moves all 0s to the front by swapping with the low pointer, then moves all 2s to the back by swapping with the high pointer, leaving 1s in the middle. After processing, the array is fully segregated.
Constraints
- 1 <= nums.length <= 100000
- nums[i] ∈ {0,1,2}
- Time complexity must be O(n)
- Space complexity must be O(1)
Optimal Approach & Strategy
Use three pointers—low, mid, high—to partition the array in a single left‑to‑right scan, swapping elements into place and maintaining constant space.
Brute Force Approach
Count the number of 0s, 1s, and 2s in one pass, then overwrite the array with that many 0s, followed by 1s, then 2s. This requires two passes and no extra memory beyond the counts.
Verified Code Solutions
function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++; mid++;
} else if (nums[mid] === 1) {
mid++;
} else { // nums[mid] === 2
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
}#include <vector>
void sortColors(std::vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
if (nums[mid] == 0) {
std::swap(nums[low++], nums[mid++]);
} else if (nums[mid] == 1) {
mid++;
} else { // nums[mid] == 2
std::swap(nums[mid], nums[high--]);
}
}
}
public class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
int temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else { // nums[mid] == 2
int temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
}
}
}
}
def sortColors(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
function sortColors(nums) {
let low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++; mid++;
} else if (nums[mid] === 1) {
mid++;
} else { // nums[mid] === 2
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
}
}
}
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.