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

Dutch National Flag समस्या

Dutch National Flag idea red, white और blue marbles को तीन neat sections में एक पास में sort करने जैसा है तीन zones रखते हुए और marbles को जगह में swap करते हुए।

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

Dutch National Flag algorithm सिर्फ तीन distinct values (आमतौर पर 0, 1, 2) वाले एक array को एक single pass में तीन grouped sections में rearrange करता है, Dutch flag की तीन horizontal color bands के नाम पर।

उदाहरण: 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

तीन pointers काम करते हैं: low उस boundary को मार्क करता है जहां तक सभी 0s रखे गए हैं, high उस boundary को मार्क करता है जहां से सभी 2s रखे गए हैं, और mid इनके बीच unprocessed middle section में scan करता है।

उदाहरण: 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

जब mid एक 0 की ओर point करता है, इसे low पर element के साथ swap किया जाता है, और low और mid दोनों आगे बढ़ते हैं, क्योंकि mid पर swapped-in value अब guaranteed रूप से एक 1 (पहले से processed) है या आगे जांचना safe है।

उदाहरण: 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

जब mid एक 2 की ओर point करता है, इसे high पर element के साथ swap किया जाता है, और high अंदर की ओर move करता है, लेकिन mid वहीं रहता है, क्योंकि mid पर नई swapped-in value अभी तक जांची नहीं गई और कुछ भी हो सकती है।

उदाहरण: 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

पूरा partition सिर्फ तीन integer pointers उपयोग करके एक O(n) pass में खत्म होता है, कोई extra array नहीं, इसे classic '0s, 1s, और 2s के एक array को sort करें' problem के लिए एक favorite efficient solution बनाते हुए।

उदाहरण: 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

Kadane का Algorithm · Prefix Sum क्या है · Two Pointer तकनीक · Sliding Window तकनीक

{# 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. #}
आम गलतियां
  1. high से swap करने के बाद mid बढ़ाना, जब swapped-in value अभी तक जांची नहीं गई और mid को रुकना चाहिए।
  2. यह भूल जाना कि low से swap करना low और mid दोनों को आगे move करता है, लेकिन 1 के लिए सिर्फ mid move होता है।
  3. mid <= high के बजाय mid < high के साथ loop करना, आखिरी element को unprocessed छोड़ते हुए।
चैप्टर सारांश
  • Arrays items को order में store करते हैं, और आप इन्हें traverse कर सकते हैं और multi-dimensional arrays के साथ काम कर सकते हैं।
  • Sliding window, two pointer, और prefix sum जैसी techniques आम array problems efficiently solve करती हैं।
  • Kadane का algorithm और Dutch National Flag 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.