Intermediate LevelData Structures & Algorithms
How does the Dutch National Flag algorithm sort an array of 0s, 1s, and 2s in O(N)?
ā Interview Prompt: Solve Sort Colors (0s, 1s, 2s) using the Dutch National Flag algorithm with O(N) time and O(1) space.
Dutch National Flag (Dijkstra) partitions an array into three sections in a single pass using three pointers.
Pointers:
ā¢
lo: boundary of 0s (left section ends here).ā¢
mid: current element being processed.ā¢
hi: boundary of 2s (right section starts here).Invariants:
ā¢
arr[0..lo-1] = all 0s.ā¢
arr[lo..mid-1] = all 1s.ā¢
arr[mid..hi] = unknown.ā¢
arr[hi+1..n-1] = all 2s.Code Implementation Example
typescript
function sortColors(nums: number[]): void {
let lo = 0, mid = 0, hi = nums.length - 1;
while (mid <= hi) {
if (nums[mid] === 0) {
[nums[lo], nums[mid]] = [nums[mid], nums[lo]];
lo++; mid++;
} else if (nums[mid] === 1) {
mid++; // 1 is in correct region
} else { // nums[mid] === 2
[nums[mid], nums[hi]] = [nums[hi], nums[mid]];
hi--; // don't advance mid ā swapped element unknown!
}
}
}
const arr = [2, 0, 2, 1, 1, 0];
sortColors(arr);
console.log(arr); // [0, 0, 1, 1, 2, 2]š”Dutch National Flag 3-way partition ā O(N) single-pass, O(1) space.
šÆ Interview Key Takeaway
Dutch National Flag is a 3-way partition running in O(N)/O(1). Key: when swapping with hi, don't advance mid ā the swapped element is unprocessed.
#DSA#Dutch National Flag#Sorting#Two Pointers#Intermediate
Back to all Data Structures & Algorithms Questionsā