Dutch National Flag Problem
Mahabharata — The Three Armies — Sorting Pandava, Kaurava, and Neutral Forces
त्रिधा विभक्तं सैन्यं च स्वस्थाने स्थापयेत् बुधः। एकेन पर्यटनेन सर्वं स्वस्थानं गच्छति॥
*The wise commander divides the army into three parts and places each in its proper position. In a single traversal, all find their rightful place.*
The Story
The final day of the Kurukshetra war approached, and the battlefield was chaos. Soldiers from three factions had become hopelessly intermingled: Pandava loyalists (marked 0), neutral observers from smaller kingdoms (marked 1), and Kaurava warriors (marked 2).
"We must reorganize before dawn," Krishna said to Arjuna. "All Pandava soldiers to the left flank, neutrals in the center, Kauravas to the right. They must be separated for the final battle."
Arjuna surveyed the jumbled formation: [2, 0, 2, 1, 1, 0, 1, 2, 0]
"I could move each soldier to a new position," he began, "checking their allegiance and placing them—"
"That would require counting first, then placing," Krishna interrupted. "Two passes. We have time for only one. And we have no auxiliary ground for a second formation."
Krishna picked up three banners and planted them along the line: - A red banner (LOW) at the leftmost position - A blue banner (MID) also at the leftmost position - A yellow banner (HIGH) at the rightmost position
"Three pointers," Krishna explained. "LOW marks the boundary of the '0' region—all positions before LOW contain 0s. HIGH marks the boundary of the '2' region—all positions after HIGH contain 2s. MID is the explorer that examines each soldier."
Arjuna watched as Krishna began:
**Initial state:** [2, 0, 2, 1, 1, 0, 1, 2, 0] LOW=0, MID=0, HIGH=8
**MID examines position 0:** Value is 2. "A Kaurava! They belong on the right. Swap with HIGH position." Swap arr[0] with arr[8]: [0, 0, 2, 1, 1, 0, 1, 2, 2] HIGH moves to 7. MID stays (must examine the new value at 0).
**MID examines position 0 again:** Value is 0. "A Pandava! They belong on the left. Swap with LOW position." But arr[LOW] = arr[0], so swap is trivial. LOW moves to 1. MID moves to 1.
**MID examines position 1:** Value is 0. "A Pandava! Swap with LOW." Swap arr[1] with arr[1] (trivial), LOW moves to 2, MID moves to 2.
**MID examines position 2:** Value is 2. "A Kaurava! Swap with HIGH." Swap arr[2] with arr[7]: [0, 0, 2, 1, 1, 0, 1, 2, 2] HIGH moves to 6. MID stays.
**MID examines position 2 again:** Value is 2. Swap with HIGH (position 6): [0, 0, 1, 1, 1, 0, 2, 2, 2] HIGH moves to 5. MID stays.
**MID examines position 2 again:** Value is 1. "A neutral! They belong in the middle. No swap needed." MID moves to 3.
**MID examines position 3:** Value is 1. MID moves to 4. **MID examines position 4:** Value is 1. MID moves to 5.
**MID examines position 5:** Value is 0. "A Pandava! Swap with LOW (position 2)." Swap arr[5] with arr[2]: [0, 0, 0, 1, 1, 1, 2, 2, 2] LOW moves to 3. MID moves to 6.
**MID (6) > HIGH (5):** Traversal complete!
Final formation: [0, 0, 0, 1, 1, 1, 2, 2, 2]
"One pass," Krishna smiled. "Each soldier examined at most once. The three pointers divided the army into three regions: 0s before LOW, 1s between LOW and HIGH, 2s after HIGH."
Arjuna marveled. "Why doesn't MID advance after swapping with HIGH?"
"Because the value swapped from HIGH is unknown—it hasn't been examined yet. We must check it before moving on. But after swapping with LOW, MID can advance because everything between LOW and MID is already confirmed to be 1."
"The invariants," Arjuna realized: - arr[0..LOW-1] = all 0s - arr[LOW..MID-1] = all 1s - arr[MID..HIGH] = unexamined - arr[HIGH+1..n-1] = all 2s
"When MID crosses HIGH, nothing is unexamined, and the sorting is complete."
This is the Dutch National Flag algorithm—three pointers sorting three values in a single pass.
Arjuna's First Instinct
Count occurrences of 0s, 1s, and 2s. Then overwrite the array with the counted values. Requires two passes and doesn't preserve relative order within groups.
public void sortColorsBruteForce(int[] nums) {
// First pass: count
int count0 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == 0) count0++;
else if (num == 1) count1++;
else count2++;
}
// Second pass: overwrite
int i = 0;
while (count0-- > 0) nums[i++] = 0;
while (count1-- > 0) nums[i++] = 1;
while (count2-- > 0) nums[i++] = 2;
}Krishna's Wisdom
public void sortColors(int[] nums) {
int low = 0; // Boundary of 0-region
int mid = 0; // Current element being examined
int high = nums.length - 1; // Boundary of 2-region
while (mid <= high) {
if (nums[mid] == 0) {
// Pandava soldier: swap to left region
swap(nums, low, mid);
low++; // 0-region grows
mid++; // Move to next (swapped value was 1 or 0, already processed)
} else if (nums[mid] == 2) {
// Kaurava soldier: swap to right region
swap(nums, mid, high);
high--; // 2-region grows
// Don't increment mid! Swapped value needs examination
} else {
// Neutral (1): already in correct region
mid++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Test with battlefield formation
public static void main(String[] args) {
int[] soldiers = {2, 0, 2, 1, 1, 0};
new Solution().sortColors(soldiers);
System.out.println(Arrays.toString(soldiers));
// Output: [0, 0, 1, 1, 2, 2]
}Step-by-Step Walkthrough
Array: [2, 0, 2, 1, 1, 0]
low=0, mid=0, high=5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=0: nums[0]=2 → Swap with high
Swap positions 0 and 5
[0, 0, 2, 1, 1, 2], high=4
(mid stays at 0 to examine swapped value)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=0: nums[0]=0 → Swap with low (trivial)
[0, 0, 2, 1, 1, 2], low=1, mid=1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=1: nums[1]=0 → Swap with low (trivial)
[0, 0, 2, 1, 1, 2], low=2, mid=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=2: nums[2]=2 → Swap with high (position 4)
Swap positions 2 and 4
[0, 0, 1, 1, 2, 2], high=3
(mid stays at 2)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=2: nums[2]=1 → Just advance mid
[0, 0, 1, 1, 2, 2], mid=3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=3: nums[3]=1 → Just advance mid
[0, 0, 1, 1, 2, 2], mid=4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
mid=4 > high=3 → DONE!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [0, 0, 1, 1, 2, 2]Deep Insight
**Why doesn't mid advance after swapping with high?**
When we swap nums[mid] with nums[high], the new value at mid came from the unexamined region. It could be 0, 1, or 2. We must examine it before moving on.
**Why CAN mid advance after swapping with low?**
The value swapped from low came from the [low, mid-1] region, which contains only 1s. So the new value at mid is guaranteed to be 1, and we can safely advance.
**The four invariants maintained:** 1. nums[0..low-1] = all 0s 2. nums[low..mid-1] = all 1s 3. nums[mid..high] = unexamined 4. nums[high+1..n-1] = all 2s
When mid > high, the unexamined region is empty, and sorting is complete.
**Edge cases:** - All same values: Works correctly (lots of trivial swaps) - Only two values present: Still works - Single element: Immediate termination - Empty array: Loop doesn't execute
**Historical note:** This algorithm is called "Dutch National Flag" because the Netherlands flag has three horizontal stripes (red, white, blue), and Edsger Dijkstra used this as a metaphor when presenting the algorithm.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Two passes: count then fill |
| Optimal | O(n) | O(1) | Single pass, each element examined at most twice |
Pattern Recognition
✅ Sort array containing only 3 distinct values ✅ In-place requirement ✅ Single-pass optimization needed ✅ "Sort colors" or "three-way partition" **LeetCode Trigger Phrases:** → "sort the array... containing 0, 1, and 2" → "three distinct values... sort in-place" → "Dutch national flag" or "three-way partitioning"
Bhagavad Gita 14.5
सत्त्वं रजस्तम इति गुणाः प्रकृतिसम्भवाः। निबध्नन्ति महाबाहो देहे देहिनमव्ययम्॥
Sattva, rajas, and tamas—these three gunas born of prakriti bind the imperishable soul to the body, O mighty-armed one.
Connection: Just as the three gunas (sattva, rajas, tamas) represent fundamental qualities that organize all of nature, the Dutch National Flag algorithm organizes elements into three distinct groups. The algorithm doesn't judge which group is superior—it simply ensures each element finds its proper place. Like a soul recognizing which guna predominates and acting accordingly, each element is examined and placed where it belongs.