Dutch National Flag problem in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include<stdio.h>

int main() {
    int a[100], n, l=0, m=0, h;
    scanf("%d", &n); h = n-1;
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    while(m <= h) {
        if(a[m]==0) { int t=a[l]; a[l++]=a[m]; a[m++]=t; }
        else if(a[m]==2) { int t=a[h]; a[h--]=a[m]; a[m]=t; }
        else m++;
    }
    for(int i=0; i<n; i++) printf("%d ", a[i]);
}

C Output

Input:  
6  
2 0 2 1 1 0  

Output:  
0 0 1 1 2 2

C++ Program

#include<iostream>
using namespace std;

int main() {
    int a[100], n, l=0, m=0, h;
    cin >> n; h = n-1;
    for(int i=0; i<n; i++) cin >> a[i];
    while(m <= h) {
        if(a[m]==0) swap(a[l++], a[m++]);
        else if(a[m]==2) swap(a[m], a[h--]);
        else m++;
    }
    for(int i=0; i<n; i++) cout << a[i] << " ";
}

C++ Output

Input:  
5  
0 1 2 0 1  

Output:  
0 0 1 1 2

JAVA Program

import java.util.*;

class DNF {
    public static void main(String[] a) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), arr[] = new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        int l=0, m=0, h=n-1;
        while(m <= h) {
            if(arr[m]==0) { int t=arr[l]; arr[l++]=arr[m]; arr[m++]=t; }
            else if(arr[m]==2) { int t=arr[h]; arr[h--]=arr[m]; arr[m]=t; }
            else m++;
        }
        for(int x : arr) System.out.print(x + " ");
    }
}

JAVA Output

Input:  
7  
2 1 0 2 1 0 1  

Output:  
0 0 1 1 1 2 2

Python Program

a = list(map(int, input().split()))
l = m = 0
h = len(a) - 1
while m <= h:
    if a[m]==0: a[l],a[m] = a[m],a[l]; l+=1; m+=1
    elif a[m]==2: a[m],a[h] = a[h],a[m]; h-=1
    else: m+=1
print(*a)

Python Output

Input:  
1 0 2 1 0  

Output:  
0 0 1 1 2

In-Depth Learning – Full Concept in Paragraphs

What Is the Dutch National Flag Problem?

The Dutch National Flag problem is the sorting problem in which the array has exactly three kinds of elements (usually 0s, 1s, and 2s), and you need to sort them in a single pass, preferably without using any additional space. The problem got its name after the Dutch flag that consists of three bands of colors — so sorting 3 different values in linear time.

This is a famous problem proposed by Edsger Dijkstra, a pioneer in algorithms and computer science.

How the Code Works

We use three pointers:

low (start of the array): where the 0s should go

mid (current element): what we’re currently inspecting

high (end of the array): where the 2s should go

Algorithm (called 3-way partitioning):

If the element is 0, swap with low and move both low and mid forward.

If it is 1, it is already in the middle; just push mid forward.

If it's 2, replace with high and reduce high (don't push mid yet because the replaced element may still require sorting).

This method guarantees that all 0s will go to the left, 2s to the right, and 1s remain in the middle.

Example

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

Step-by-step:

Replace 2 with last → [1, 0, 1, 2, 0, 2]

1 is fine → [1, 0, 1, 2, 0, 2]

Swap 0 with 1st → [0, 1, 1, 2, 0, 2]

1 is fine

Swap 0 with second 1 → [0, 0, 1, 2, 1, 2]

Done

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

Real-Life Analogy

Suppose you're sorting red, white, and blue colored balls into 3 boxes.

You don't want to use extra boxes,

You just want to organize them in-place.

You take one ball at a time and place it in its proper place right away. This is similar to the Dutch National Flag logic — dividing 3 disparate categories with few swaps.

Where and When Is It Used?

This algorithm is commonly used in:

Sorting arrays of restricted range values (such as 0, 1, 2)

Color or category sorting

Partitioning logic within quicksort

Memory-constrained applications

Embedded systems where space and time matter

Interviewers ask this frequently in TCS, Infosys, Amazon, Google, and Microsoft to verify your familiarity with in-place sorting and pointer manipulation.

Time and Space Complexity

Metric Value

Time O(n) — Single pass

Space O(1) — No extra array

Stability Not stable (can change relative order)

Python-Specific Tip

Python makes this reasoning neat using tuple unpacking:

python

a[l], a[m] = a[m], a[l]  # swap 0

a[m], a[h] = a[h], a[m]  # swap 2

This makes the code concise, unambiguous, and legible.

SEO-Optimized Natural Paragraph for Ranking

Need to solve the Dutch National Flag problem (sort 0s, 1s, and 2s) in C, C++, Java, or Python? This tutorial demonstrates how to apply the three-pointer method to sort arrays with only three different elements in a single pass without the use of additional space. Frequently asked in coding competitions and technical interviews, this algorithm is regarded as efficient, logical, and applicable in real-world scenarios. Be it for TCS, Infosys, Amazon, or Google interviews, learning this method will make you able to crack many array and partitioning problems at one go.