Dutch National Flag problem and solution in Java and Python

The Dutch National Flag problem is a classic DSA (Data Structures & Algorithms) question frequently asked in technical interviews (especially from the sorting and two-pointer category).

Let’s break it down in simple steps 👇

---

🇳🇱 Dutch National Flag Problem

🧩 Problem Statement

Given an array containing only 0s, 1s, and 2s, sort the array in-place so that all 0s come first, then all 1s, and then all 2s.

You must solve it without using built-in sort functions and in O(n) time and O(1) space.

---

Example

Input:

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

Output:

[0, 0, 1, 1, 2, 2]

---

🎯 Intuition

This problem was proposed by Edsger Dijkstra (a famous computer scientist from the Netherlands). The key idea is to partition the array into three sections using three pointers:

• low → boundary for 0s
• mid → current element under consideration
• high → boundary for 2s

At any point:

[0 ... low-1] → all 0s
[low ... mid-1] → all 1s
[mid ... high] → unknown
[high+1 ... end] → all 2s

---

⚙️ Algorithm Steps

1. Initialize:

   low = 0, mid = 0, high = n - 1
   

2. Traverse while mid <= high:

   • If nums[mid] == 0: Swap nums[low] and nums[mid]; increment both low and mid.
   • Else if nums[mid] == 1: Just increment mid.
   • Else if nums[mid] == 2: Swap nums[mid] and nums[high]; decrement high.

---

✅ Java Solution

import java.util.Arrays;

public class DutchNationalFlag {
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }
}

Output:

[0, 0, 1, 1, 2, 2]

---

✅ Python Solution

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

    return nums

# Example
nums = [2, 0, 2, 1, 1, 0]
print(sortColors(nums))  # Output: [0, 0, 1, 1, 2, 2]

---

🧠 Complexity Analysis

Type	Complexity
Time	O(n) — each element is checked at most once
Space	O(1) — in-place sorting
Algorithm Type	3-way partition / Two-pointer method

---

🧩 Variations

1. Sort array of 0s, 1s, and 2s (LeetCode #75) — classic version.
2. Sort colors with more than 3 categories — generalize partition logic.
3. Partition array around a pivot (like QuickSort’s partition step).
4. Sort balls by color, size, or type using the same 3-pointer technique.

---