← Back to DSA Course | Chapter 2: Arrays | Lesson 8 of 8

Dutch National Flag

The Dutch National Flag idea is like sorting red, white and blue marbles into three neat sections in one pass by keeping three zones and swapping marbles into place.

In this page:

  1. Three-way Partition Idea
  2. Low, Mid, and High
  3. Handling Zero
  4. Handling Two
  5. Dutch National Flag Practice
Syntax
markup 
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
    if arr[mid] == 0:
        arr[low], arr[mid] = arr[mid], arr[low]
        low += 1
        mid += 1
    elif arr[mid] == 1:
        mid += 1
    else:
        arr[mid], arr[high] = arr[high], arr[mid]
        high -= 1

Three-way Partition Idea

The Dutch National Flag algorithm rearranges an array containing only three distinct values (commonly 0, 1, 2) into three grouped sections in a single pass, named after the three horizontal color bands of the Dutch flag.

Example: Three-way Partition Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 0, 1, 2, 1, 0};
    int n = 6, low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
        else if (arr[mid] == 1) mid++;
        else swap(arr[mid], arr[high--]);
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 0, 1, 2, 1, 0};
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) { int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t; low++; mid++; }
            else if (arr[mid] == 1) mid++;
            else { int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t; high--; }
        }
        for (int x : arr) System.out.print(x + " ");
    }
}
arr = [2, 0, 1, 2, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
    if arr[mid] == 0:
        arr[low], arr[mid] = arr[mid], arr[low]
        low += 1; mid += 1
    elif arr[mid] == 1:
        mid += 1
    else:
        arr[mid], arr[high] = arr[high], arr[mid]
        high -= 1
print(arr)
#include <stdio.h>
int main() {
    int arr[] = {2, 0, 1, 2, 1, 0};
    int n = 6, low = 0, mid = 0, high = n - 1, t;
    while (mid <= high) {
        if (arr[mid] == 0) { t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
        else if (arr[mid] == 1) mid++;
        else { t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
    }
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Low, Mid, and High

Three pointers do the work: low marks the boundary up to which all 0s have been placed, high marks the boundary from which all 2s have been placed, and mid scans through the unprocessed middle section between them.

Example: Low, Mid, and High

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 0, 2, 1, 0};
    int n = 5, low = 0, mid = 0, high = n - 1;
    cout << "low=" << low << " (boundary for 0s), mid=" << mid << " (scanner), high=" << high << " (boundary for 2s)" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 0};
        int low = 0, mid = 0, high = arr.length - 1;
        System.out.println("low=" + low + " (boundary for 0s), mid=" + mid + " (scanner), high=" + high + " (boundary for 2s)");
    }
}
arr = [1, 0, 2, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
print(f"low={low} (boundary for 0s), mid={mid} (scanner), high={high} (boundary for 2s)")
#include <stdio.h>
int main() {
    int arr[] = {1, 0, 2, 1, 0};
    int n = 5, low = 0, mid = 0, high = n - 1;
    printf("low=%d (boundary for 0s), mid=%d (scanner), high=%d (boundary for 2s)\n", low, mid, high);
    return 0;
}

Handling Zero

When mid points to a 0, it's swapped with the element at low, and both low and mid advance, since the swapped-in value at mid is now guaranteed to be a 1 (already processed) or safe to check next.

Example: Handling Zero

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 0, 2};
    int low = 0, mid = 1;
    cout << "Before: arr[mid]=" << arr[mid] << endl;
    swap(arr[low], arr[mid]);
    low++; mid++;
    cout << "After swap with low: arr[0]=" << arr[0] << ", low=" << low << ", mid=" << mid << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 0, 2};
        int low = 0, mid = 1;
        System.out.println("Before: arr[mid]=" + arr[mid]);
        int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
        low++; mid++;
        System.out.println("After swap with low: arr[0]=" + arr[0] + ", low=" + low + ", mid=" + mid);
    }
}
arr = [1, 0, 2]
low, mid = 0, 1
print("Before: arr[mid]=", arr[mid])
arr[low], arr[mid] = arr[mid], arr[low]
low += 1; mid += 1
print(f"After swap with low: arr[0]={arr[0]}, low={low}, mid={mid}")
#include <stdio.h>
int main() {
    int arr[] = {1, 0, 2};
    int low = 0, mid = 1, t;
    printf("Before: arr[mid]=%d\n", arr[mid]);
    t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
    low++; mid++;
    printf("After swap with low: arr[0]=%d, low=%d, mid=%d\n", arr[0], low, mid);
    return 0;
}

Handling Two

When mid points to a 2, it's swapped with the element at high, and high moves inward, but mid stays put, because the newly swapped-in value at mid hasn't been checked yet and could be anything.

Example: Handling Two

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 0};
    int mid = 1, high = 2;
    cout << "Before: arr[mid]=" << arr[mid] << endl;
    swap(arr[mid], arr[high]);
    high--;
    cout << "After swap with high: arr[mid]=" << arr[mid] << ", mid stays=" << mid << ", high=" << high << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 0};
        int mid = 1, high = 2;
        System.out.println("Before: arr[mid]=" + arr[mid]);
        int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
        high--;
        System.out.println("After swap with high: arr[mid]=" + arr[mid] + ", mid stays=" + mid + ", high=" + high);
    }
}
arr = [1, 2, 0]
mid, high = 1, 2
print("Before: arr[mid]=", arr[mid])
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
print(f"After swap with high: arr[mid]={arr[mid]}, mid stays={mid}, high={high}")
#include <stdio.h>
int main() {
    int arr[] = {1, 2, 0};
    int mid = 1, high = 2, t;
    printf("Before: arr[mid]=%d\n", arr[mid]);
    t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
    high--;
    printf("After swap with high: arr[mid]=%d, mid stays=%d, high=%d\n", arr[mid], mid, high);
    return 0;
}

Dutch National Flag Practice

The whole partition finishes in one O(n) pass using only three integer pointers, no extra array, making it a favorite efficient solution for the classic 'sort an array of 0s, 1s, and 2s' problem.

Example: Dutch National Flag Practice

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int n = 6, low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
        else if (arr[mid] == 1) mid++;
        else swap(arr[mid], arr[high--]);
    }
    cout << "Sorted: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) { int t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
            else if (arr[mid] == 1) mid++;
            else { int t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
        }
        System.out.print("Sorted: ");
        for (int x : arr) System.out.print(x + " ");
    }
}
arr = [2, 0, 2, 1, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
    if arr[mid] == 0:
        arr[low], arr[mid] = arr[mid], arr[low]; low += 1; mid += 1
    elif arr[mid] == 1:
        mid += 1
    else:
        arr[mid], arr[high] = arr[high], arr[mid]; high -= 1
print("Sorted:", arr)
#include <stdio.h>
int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int n = 6, low = 0, mid = 0, high = n - 1, t;
    while (mid <= high) {
        if (arr[mid] == 0) { t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
        else if (arr[mid] == 1) mid++;
        else { t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
    }
    printf("Sorted: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
Related Topics

Kadanes Algorithm · Prefix Sum · Two Pointer Technique · Sliding Window Technique

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Increasing mid after swapping with high, when the swapped-in value has not been checked yet and mid must stay.
  2. Forgetting that swapping with low moves both low and mid forward, but for 1 only mid moves.
  3. Looping while mid < high instead of mid <= high, leaving the last element unprocessed.
Chapter Summary
  • Arrays store items in order, and you can traverse them and work with multi-dimensional arrays.
  • Techniques like sliding window, two pointer, and prefix sum solve common array problems efficiently.
  • Kadane's algorithm and the Dutch National Flag are classic array algorithms.
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Kadanes Algorithm Next Lesson → String Introduction

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.