Dutch National Flag Three Way Partition in DSA C# - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Start with array and pivot

↓

Initialize low, mid, high pointers

↓

Check mid <= high?

No→Done

Yes↓

Compare arr[mid

↓

Swap arr[low

↓

low++, mid++

↩Back to check mid <= high

The algorithm uses three pointers to partition the array into three parts: less than pivot, equal to pivot, and greater than pivot, by swapping elements and moving pointers until mid passes high.

Execution Sample

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) { Swap(arr, low++, mid++); }
  else if (arr[mid] == pivot) { mid++; }
  else { Swap(arr, mid, high--); }
}

This code partitions the array so that all 0s come first, then 1s, then 2s, using three pointers and swaps.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2, 0, 2, 1, 1, 0]	Initial pointers set
2	arr[mid]=2 > pivot=1, swap arr[mid] and arr[high]	0	0	5	[0, 0, 2, 1, 1, 2]	Swap arr[0] and arr[5], high-- to 4
3	arr[mid]=0 < pivot=1, swap arr[low] and arr[mid]	0	0	4	[0, 0, 2, 1, 1, 2]	Swap arr[0] and arr[0], low++ to 1, mid++ to 1
4	arr[mid]=0 < pivot=1, swap arr[low] and arr[mid]	1	1	4	[0, 0, 2, 1, 1, 2]	Swap arr[1] and arr[1], low++ to 2, mid++ to 2
5	arr[mid]=2 > pivot=1, swap arr[mid] and arr[high]	2	2	4	[0, 0, 1, 1, 2, 2]	Swap arr[2] and arr[4], high-- to 3
6	arr[mid]=1 == pivot=1, mid++	2	2	3	[0, 0, 1, 1, 2, 2]	mid++ to 3
7	arr[mid]=1 == pivot=1, mid++	2	3	3	[0, 0, 1, 1, 2, 2]	mid++ to 4
8	mid=4 > high=3, done	2	4	3	[0, 0, 1, 1, 2, 2]	Loop ends

💡 mid pointer passed high pointer, partition complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
low	0	0	1	2	2	2	2	2
mid	0	0	1	2	2	3	4	4
high	5	4	4	4	3	3	3	3
arr	[2,0,2,1,1,0]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]

Key Moments - 3 Insights

Why do we not increment mid when arr[mid] > pivot and we swap with arr[high]?

Because after swapping with arr[high], the new element at mid is unprocessed, so we must check it again. This is shown in step 5 where mid stays at 2 after swap.

Why do we increment both low and mid when arr[mid] < pivot?

Because swapping arr[low] and arr[mid] places a smaller element at low, so low moves forward. mid also moves forward since the element at mid is now processed. See steps 3 and 4.

When does the loop stop?

The loop stops when mid pointer passes high pointer, meaning all elements are partitioned. This is shown in step 8.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'high' after step 5?

A 5

B 3

C 4

D 2

💡 Hint

Check the 'high' column in the execution_table row for step 5.

At which step does the 'mid' pointer first increment without swapping?

A Step 3

B Step 2

C Step 6

D Step 4

💡 Hint

Look for the step where operation is 'arr[mid] == pivot' and mid increments.

If the pivot was 0 instead of 1, how would the array state change after step 3?

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

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

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

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

💡 Hint

Consider how swapping happens when arr[mid] < pivot with pivot=0 at step 3.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- Elements < pivot go to front (swap with low)
- Elements == pivot stay in middle (mid++)
- Elements > pivot go to end (swap with high)
- Continue until mid > high
- In-place, single pass, O(n) time

Full Transcript

The Dutch National Flag algorithm partitions an array into three parts based on a pivot value. It uses three pointers: low, mid, and high. Initially, low and mid start at the beginning, high at the end. While mid is less than or equal to high, the element at mid is compared to the pivot. If less, it is swapped with the element at low, and both low and mid move forward. If equal, mid moves forward. If greater, it is swapped with the element at high, and high moves backward. This process continues until mid passes high, resulting in a partitioned array with elements less than pivot first, then equal, then greater. The execution table traces each step, showing pointer positions and array state changes. Key moments clarify why mid does not always move after swaps and when the loop ends.

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