Dutch National Flag Three Way Partition in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on an array

What is the output of the following C# code that partitions the array using the Dutch National Flag algorithm with pivot = 1?

DSA C#

int[] arr = {2, 0, 2, 1, 1, 0};
int pivot = 1;
int low = 0, mid = 0, high = arr.Length - 1;
while (mid <= high)
{
    if (arr[mid] < pivot)
    {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
        low++;
        mid++;
    }
    else if (arr[mid] == pivot)
    {
        mid++;
    }
    else
    {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
        high--;
    }
}
Console.WriteLine(string.Join(", ", arr));

A 2, 2, 1, 1, 0, 0

B 0, 0, 1, 1, 2, 2

C 0, 1, 0, 1, 2, 2

D 1, 1, 0, 0, 2, 2

💡 Hint

Remember the algorithm moves elements less than pivot to the front, equal stay in middle, and greater to the end.

The Dutch National Flag algorithm partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. After processing, the array becomes sorted as 0, 0, 1, 1, 2, 2.

🧠 Conceptual

intermediate

Number of swaps in Dutch National Flag algorithm

Given an array of size n with only three distinct values, what is the maximum number of swaps the Dutch National Flag algorithm performs in the worst case?

A n

B 2n

C n/2

D n^2

💡 Hint

Each element is swapped at most once or twice during partitioning.

The algorithm processes each element at most once, and each swap moves an element closer to its final position. Hence, the maximum swaps are proportional to n.

🔧 Debug

advanced

Identify the bug in this Dutch National Flag implementation

What error does the following C# code produce when run on array {1, 0, 2} with pivot = 1?

DSA C#

int[] arr = {1, 0, 2};
int pivot = 1;
int low = 0, mid = 0, high = arr.Length - 1;
while (mid < high)
{
    if (arr[mid] < pivot)
    {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
        low++;
        mid++;
    }
    else if (arr[mid] == pivot)
    {
        mid++;
    }
    else
    {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
        high--;
    }
}
Console.WriteLine(string.Join(", ", arr));

A Throws IndexOutOfRangeException

B The code runs correctly and outputs: 0, 1, 2

C The code runs infinitely (infinite loop)

D Outputs unsorted array: 0, 2, 1

💡 Hint

Check the loop condition and how mid and high pointers move.

The code runs correctly for this specific array {1, 0, 2}, outputting 0, 1, 2. However, the loop condition 'mid < high' can lead to incorrect partitioning in other cases (e.g., {2, 0, 1} outputs 1, 0, 2 instead of 0, 1, 2) because it skips processing when mid == high.

🚀 Application

advanced

Using Dutch National Flag to sort colors

You have an array representing colors coded as 0 (red), 1 (white), and 2 (blue). Which code snippet correctly sorts the array in one pass using Dutch National Flag algorithm?

A

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

B Array.Sort(arr);

C

for (int i = 0; i < arr.Length; i++) {
  for (int j = i + 1; j < arr.Length; j++) {
    if (arr[i] > arr[j]) Swap(arr, i, j);
  }
}

D

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

💡 Hint

Dutch National Flag uses three pointers and swaps based on comparison with pivot.

Option D implements the classic Dutch National Flag algorithm with three pointers and swaps in one pass. Other options are either sorting by built-in or inefficient methods or incomplete logic.

🧠 Conceptual

expert

Why Dutch National Flag algorithm is O(n) and not O(n^2)?

Why does the Dutch National Flag algorithm run in linear time O(n) instead of quadratic O(n^2) despite nested swaps?

A Because each element is visited and swapped at most once, the pointers only move forward or backward without revisiting elements.

B Because the algorithm uses recursion to divide the array into smaller parts.

C Because it sorts the array using a built-in efficient sort internally.

D Because it only swaps elements when they are equal to the pivot.

💡 Hint

Think about how many times each element is processed and how pointers move.

The algorithm uses three pointers that move through the array once. Each swap moves an element closer to its final position, so no element is processed multiple times, resulting in O(n) time.

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