Dutch National Flag Three Way Partition in DSA C#

Mental Model

We rearrange an array into three parts: smaller than pivot, equal to pivot, and greater than pivot, all in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick each ball once and put it in the right bin without extra space.

Index:  0   1   2   3   4   5   6
Array: [2] [0] [2] [1] [1] [0] [2]
Pointers:
 low ↑    mid ↑          high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0, 2], pivot = 1

Goal: Rearrange array so that all 0s come first, then all 1s, then all 2s

Step 1: Check element at mid=0 (value 2), swap with element at high=6, decrease high

[2] [0] [2] [1] [1] [0] [2]
low=0 mid=0 high=5

Why: 2 is greater than pivot 1, so move it to the end by swapping with high

Step 2: Check element at mid=0 (value 2), swap with element at high=5, decrease high

[0] [0] [2] [1] [1] [2] [2]
low=0 mid=0 high=4

Why: Again 2 is greater than pivot, swap with high to move it to the end

Step 3: Check element at mid=0 (value 0), swap with element at low=0, increase low and mid

[0] [0] [2] [1] [1] [2] [2]
low=1 mid=1 high=4

Why: 0 is less than pivot, move it to the front by swapping with low

Step 4: Check element at mid=1 (value 0), swap with element at low=1, increase low and mid

[0] [0] [2] [1] [1] [2] [2]
low=2 mid=2 high=4

Why: 0 is less than pivot, move it to the front

Step 5: Check element at mid=2 (value 2), swap with element at high=4, decrease high

[0] [0] [1] [1] [2] [2] [2]
low=2 mid=2 high=3

Why: 2 is greater than pivot, move it to the end

Step 6: Check element at mid=2 (value 1), mid increases

[0] [0] [1] [1] [2] [2] [2]
low=2 mid=3 high=3

Why: 1 equals pivot, just move mid forward

Step 7: Check element at mid=3 (value 1), mid increases

[0] [0] [1] [1] [2] [2] [2]
low=2 mid=4 high=3

Why: 1 equals pivot, move mid forward; mid now > high, stop

Result:

[0] -> [0] -> [1] -> [1] -> [2] -> [2] -> [2] -> null

Annotated Code

DSA C#

using System;

class DutchNationalFlag
{
    public static void ThreeWayPartition(int[] arr, int pivot)
    {
        int low = 0, mid = 0, high = arr.Length - 1;
        while (mid <= high)
        {
            if (arr[mid] < pivot)
            {
                // Swap arr[low] and arr[mid], move both pointers forward
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;
                low++;
                mid++;
            }
            else if (arr[mid] == pivot)
            {
                // Element equals pivot, just move mid forward
                mid++;
            }
            else
            {
                // arr[mid] > pivot, swap with arr[high], move high backward
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    static void PrintArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main()
    {
        int[] arr = { 2, 0, 2, 1, 1, 0, 2 };
        int pivot = 1;
        ThreeWayPartition(arr, pivot);
        PrintArray(arr);
    }
}

while (mid <= high)

continue processing until mid passes high

if (arr[mid] < pivot)

if current element less than pivot, swap with low and advance low and mid

int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp; low++; mid++;

swap to move smaller element to front and advance pointers

else if (arr[mid] == pivot) mid++;

if equal to pivot, just move mid forward

else { swap arr[mid] and arr[high]; high--; }

if greater than pivot, swap with high and decrease high

Output

0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer moving forward

Space: O(1) because rearrangement is done in place without extra storage

vs Alternative: Compared to sorting the entire array O(n log n), this is faster and uses no extra space

Edge Cases

empty array

function completes immediately without changes

DSA C#

while (mid <= high) -- loop does not start if array is empty

all elements equal to pivot

mid moves through array without swaps, array stays same

DSA C#

else if (arr[mid] == pivot) mid++;

array with only two distinct values

elements less than pivot moved to front, others to end

DSA C#

if (arr[mid] < pivot) and else block handle this

When to Use This Pattern

When you need to partition an array into three groups around a pivot in one pass, use Dutch National Flag to efficiently rearrange with constant space.

Common Mistakes

Mistake: Advancing mid pointer after swapping with high without checking the swapped element
Fix: Do not advance mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping elements incorrectly causing infinite loops or missed elements
Fix: Always swap with correct pointers and update pointers carefully to avoid skipping elements

Summary

Rearranges an array into three parts: less than, equal to, and greater than a pivot value in one pass.

Use when you want to sort or partition arrays with three categories efficiently without extra space.

The key is to use three pointers to track boundaries and swap elements to their correct regions in one scan.

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To rearrange an array into three parts based on a pivot value

B. To sort an array in ascending order

C. To find the maximum element in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the algorithm's purpose

   The Dutch National Flag algorithm partitions an array into three parts: less than, equal to, and greater than a pivot.

2. Step 2: Compare with other options

   Sorting or finding max are different tasks; reversing is unrelated.

3. Final Answer:

   To rearrange an array into three parts based on a pivot value -> Option A

4. Quick Check:

   Partitioning = Rearranging into three parts [OK]

Hint: Remember: It splits array into three groups around a pivot [OK]

Common Mistakes:

• Confusing partitioning with sorting
• Thinking it finds max or min values
• Assuming it reverses the array

2. Which of the following is the correct C# syntax to swap two elements arr[i] and arr[j] in an array?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr.Swap(i, j);

Solution

1. Step 1: Understand swapping in C# arrays

   Swapping requires a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly; B overwrites values; C and D are invalid syntax in C#.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Swap needs temp variable [OK]

Hint: Use a temp variable to swap two array elements [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using non-existent swap functions
• Confusing syntax from other languages

3. What will be the output array after applying the Dutch National Flag partition on arr = [2, 0, 2, 1, 1, 0] with pivot = 1?

medium

A. [1, 1, 0, 0, 2, 2]

B. [2, 2, 1, 1, 0, 0]

C. [0, 0, 1, 1, 2, 2]

D. [0, 1, 2, 0, 1, 2]

Solution

1. Step 1: Partition array around pivot 1

   Elements less than 1: 0,0; equal to 1: 1,1; greater than 1: 2,2.

2. Step 2: Arrange in order less, equal, greater

   Resulting array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option C

4. Quick Check:

   Partitioned array = [0,0,1,1,2,2] [OK]

Hint: Group elements less, equal, then greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Ignoring pivot value placement

4. Identify the error in this C# code snippet for Dutch National Flag partition:

int low = 0, mid = 0, high = arr.Length - 1;
while (mid <= high) {
  if (arr[mid] < pivot) {
    Swap(arr[low], arr[mid]);
    low++;
    mid++;
  } else if (arr[mid] == pivot) {
    mid++;
  } else {
    Swap(arr[mid], arr[high]);
    high--;
  }
}

medium

A. Variables low, mid, high are not declared

B. Loop condition should be mid < high, not mid <= high

C. Pivot value is not initialized

D. Swap method is called incorrectly; should swap array elements by index

Solution

1. Step 1: Check Swap usage

   Swap(arr[low], arr[mid]) passes values, not indices; swapping values won't affect array elements.

2. Step 2: Correct swap call

   Swap should be a method swapping elements by indices or use a temp variable to swap arr[low] and arr[mid].

3. Final Answer:

   Swap method is called incorrectly; should swap array elements by index -> Option D

4. Quick Check:

   Swap must affect array elements, not just values [OK]

Hint: Swap array elements by index, not by passing values [OK]

Common Mistakes:

• Passing values instead of indices to swap
• Incorrect loop boundary conditions
• Forgetting to initialize pivot

5. Given an array arr = [3, 5, 2, 3, 8, 3, 1] and pivot = 3, how would you modify the Dutch National Flag algorithm to partition the array so that all elements less than 3 come first, then all elements equal to 3, and finally all elements greater than 3? What is the final array?

hard

A. [2, 1, 3, 3, 3, 5, 8]

B. [1, 2, 3, 3, 3, 8, 5]

C. [3, 3, 3, 2, 1, 5, 8]

D. [5, 8, 3, 3, 3, 2, 1]

Solution

1. Step 1: Apply Dutch National Flag partition with pivot 3

   Group elements less than 3: 1,2; equal to 3: 3,3,3; greater than 3: 5,8.

2. Step 2: Arrange groups in order less, equal, greater

   Final array is [2, 1, 3, 3, 3, 5, 8].

3. Final Answer:

   [2, 1, 3, 3, 3, 5, 8] -> Option A

4. Quick Check:

   Partitioned array = [2,1,3,3,3,5,8] [OK]

Hint: Place less, equal, then greater elements around pivot [OK]

Common Mistakes:

• Mixing order of groups
• Not grouping all equal elements together
• Ignoring elements equal to pivot