The Logic Behind 0s, 1s, and 2s (DNF)

🚩 Mastering the Dutch National Flag Algorithm in C++

Sorting 0s, 1s, and 2s in a single pass? That's the power of the Dutch National Flag Algorithm, an elegant algorithm designed by computer scientist Edsger Dijkstra. It's an essential technique in your DSA toolbox!

---

📌 Problem Statement

You're given an array consisting only of 0s, 1s, and 2s. Your task is to sort the array in-place in a single pass so that:

• All 0s appear first
• All 1s appear next
• All 2s appear last

Input: nums = [2, 0, 2, 1, 1, 0]

Output: nums = [0, 0, 1, 1, 2, 2]

---

🤔 Real-Life Analogy

Imagine you have a bucket of red, white, and blue balls. You want to group them together in the order of colors — this is exactly what the Dutch National Flag problem is about!

---

📚 Understanding the Concept

The Dutch National Flag problem can be solved by maintaining three pointers:

• low: to track the position where the next 0 should be placed.
• mid: the current element being evaluated.
• high: to track the position where the next 2 should go.

The idea is to:

• Swap 0s to the beginning.
• Leave 1s in the middle.
• Swap 2s to the end.

🧠 Table to Understand Swapping:

Index	Before Action	After Action (if nums[mid] == 0)
0	2	0
1	0	2
	swap(nums[low], nums[mid])
	++low, ++mid	++low, ++mid

---

🌀 Naive Approach

Use a counting sort-like method.

🧾 Steps:

1. Count the number of 0s, 1s, and 2s.
2. Overwrite the original array with counted values.

⏱ Time: O(n)

🧠 Space: O(1)

cpp
void sortColors(vector<int>& nums) {
    int zero = 0, one = 0, two = 0;
    for (int num : nums) {
        if (num == 0) zero++;
        else if (num == 1) one++;
        else two++;
    }

    int i = 0;
    while (zero--) nums[i++] = 0;
    while (one--) nums[i++] = 1;
    while (two--) nums[i++] = 2;
}

⚡ Optimized One-Pass Approach (Dutch National Flag Algorithm)

🚀 Algorithm Steps:

1. Initialize low = 0, mid = 0, and high = n - 1.

2. While mid <= high, check:

3. If nums[mid] == 0: swap with nums[low], increment low and mid.

4. If nums[mid] == 1: just increment mid.

5. If nums[mid] == 2: swap with nums[high], decrement high.

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)

💻 Code:

cpp

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++; mid++;
        }
        else if (nums[mid] == 1) {
            mid++;
        }
        else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

🧪 Dry Run Example

Input: [2, 0, 2, 1, 1, 0]
Initial: low = 0, mid = 0, high = 5

Step 1: swap(nums[0], nums[5]) -> [0, 0, 2, 1, 1, 2]
low = 0, mid = 0, high = 4

Step 2: nums[0] == 0 => swap(nums[0], nums[0]) => low++, mid++`

Final: [0, 0, 1, 1, 2, 2]

🔗 Related Problems to Practice

• Sort Colors
• Sort Array by Parity
• Wiggle Sort
• Rainbow Sort

🎯 When to Use Dutch National Flag?

• When the array contains 3 distinct categories or values.
• You want to sort in-place with constant space.
• Common in segregation problems, such as even/odd, 0s/1s, red/blue/green, etc.

🚀 Open Source Contribution

I'm solving DSA problems in C++ and uploading them algorithm-wise to GitHub.
Feel free to check it out, use the solutions, or contribute!

👉 📁 DSA-in-C++ GitHub Repository