DNF Intro

Sorting problems are everywhere in the world of DSA. One common category is sorting arrays with only a few distinct elements. That’s where the Dutch National Flag Algorithm shines!

This post is a complete guide to mastering this algorithm – packed with examples, code, visual intuition, and real-world use cases. Whether you're preparing for your next tech interview or contributing to open source, this guide has you covered.

---

📌 What is the Dutch National Flag Algorithm?

The Dutch National Flag Algorithm (DNF) was proposed by Edsger Dijkstra. It solves the problem of sorting an array containing only three types of elements, such as:

• 0s, 1s, and 2s

• red, white, and blue

• low, medium, and high

The name "Dutch National Flag" comes from the three-color flag of the Netherlands (red, white, and blue).

---

🔍 Problem Statement

Given an array nums consisting of only 0s, 1s, and 2s, sort the array in linear time and constant space without using any library sort function.

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

---

🧠 Intuition Behind the Algorithm

We want to partition the array into three parts:

1. All 0s on the left

2. All 1s in the middle

3. All 2s on the right

We use three pointers:

• low → position for next 0

• mid → current element

• high → position for next 2

Based on the value at nums[mid], we take the following actions:

• If nums[mid] == 0, swap with nums[low] and move both low and mid forward.

• If nums[mid] == 1, move only mid forward.

• If nums[mid] == 2, swap with nums[high] and move high backward.

---

🐌 Naive / Brute-Force Approach

🔸 Count the frequency of 0s, 1s, and 2s

🔸 Overwrite the array in that order

cppCopyEditvoid sortColors(vector<int>& nums) {
    int count0 = 0, count1 = 0, count2 = 0;
    for (int num : nums) {
        if (num == 0) count0++;
        else if (num == 1) count1++;
        else count2++;
    }

    for (int i = 0; i < count0; i++) nums[i] = 0;
    for (int i = count0; i < count0 + count1; i++) nums[i] = 1;
    for (int i = count0 + count1; i < nums.size(); i++) nums[i] = 2;
}

⏱ Time Complexity: O(N)
🧠 Space Complexity: O(1)

Not in-place optimized. Requires multiple passes.

---

🚀 Optimized Approach: Dutch National Flag (In-place)

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

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

⏱ Time Complexity: O(N)
🧠 Space Complexity: O(1)
✔️ In-place, one-pass

---

📊 Visual Representation

Imagine three buckets:

csharpCopyEditlow       mid        high
 ↓         ↓           ↓
[0s | 1s | unsorted | 2s]

The mid pointer decides which element goes to which bucket (left for 0s, right for 2s, center for 1s).

---

📚 Related Problems

• Sort Colors (Leetcode 75)

• Sort Array by Parity

• Wiggle Sort

• Three-way Partitioning (GFG)

---

🧠 Real-World Applications

• Sorting arrays with limited distinct elements

• Segregating low/medium/high priority tasks

• Preprocessing buckets in radix/bucket sort

---

🔓 Open Source Contribution

💻 I'm building an open-source DSA in C++ GitHub Repository.
This includes categorized folders like Arrays → Dutch National Flag → Code files.

Feel free to contribute and explore!
🚀 Let's grow and learn together through Open Source.

---

✍️ Final Words

The Dutch National Flag Algorithm is a powerful tool in your DSA toolbox – simple yet elegant. Understanding its in-place partitioning logic is essential for cracking a wide range of interview questions.

🔁 Happy Coding & Keep Solving!
🧠 Follow me for more algorithm deep dives!

#DSA #Algorithms #Coding #Cpp #InterviewPrep #TechBlog

#DataStructuresAndAlgorithms #LeetCode #OpenSource #Hashnode

#DevCommunity #Programming #SoftwareEngineering #SortingAlgorithms

#DutchNationalFlag #CodeNewbie #100DaysOfCode #LearnToCode