Dutch National Flag Three Way Partition in DSA Java - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Initialize pointers: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Check arr[mid

↓

Swap arr[low

↓

low++, mid++

↓

high--

↓

Repeat loop

We use three pointers low, mid, and high to partition the array into three parts: 0s, 1s, and 2s by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA Java

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

This code partitions an array of 0s, 1s, and 2s so that all 0s come first, then 1s, then 2s.

Execution Table

Step	Operation	Pointers (low, mid, high)	Array State	Action/Swap
1	Initialize pointers	(0, 0, 8)	[2, 0, 2, 1, 1, 0, 0, 2, 1]	Start
2	Check arr[mid]=2	(0, 0, 8)	[2, 0, 2, 1, 1, 0, 0, 2, 1]	Swap arr[mid] and arr[high], high--
3	After swap	(0, 0, 7)	[1, 0, 2, 1, 1, 0, 0, 2, 2]	Swapped arr[0] and arr[8]
4	Check arr[mid]=1	(0, 0, 7)	[1, 0, 2, 1, 1, 0, 0, 2, 2]	mid++
5	After mid++	(0, 1, 7)	[1, 0, 2, 1, 1, 0, 0, 2, 2]	Moved mid to 1
6	Check arr[mid]=0	(0, 1, 7)	[1, 0, 2, 1, 1, 0, 0, 2, 2]	Swap arr[low] and arr[mid], low++, mid++
7	After swap	(1, 2, 7)	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swapped arr[0] and arr[1]
8	Check arr[mid]=2	(1, 2, 7)	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swap arr[mid] and arr[high], high--
9	After swap	(1, 2, 6)	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swapped arr[2] and arr[7]
10	Check arr[mid]=2	(1, 2, 6)	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swap arr[mid] and arr[high], high--
11	After swap	(1, 2, 5)	[0, 1, 0, 1, 1, 0, 2, 2, 2]	Swapped arr[2] and arr[6]
12	Check arr[mid]=0	(1, 2, 5)	[0, 1, 0, 1, 1, 0, 2, 2, 2]	Swap arr[low] and arr[mid], low++, mid++
13	After swap	(2, 3, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	Swapped arr[1] and arr[2]
14	Check arr[mid]=1	(2, 3, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	mid++
15	After mid++	(2, 4, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	Moved mid to 4
16	Check arr[mid]=1	(2, 4, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	mid++
17	After mid++	(2, 5, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	Moved mid to 5
18	Check arr[mid]=0	(2, 5, 5)	[0, 0, 1, 1, 1, 0, 2, 2, 2]	Swap arr[low] and arr[mid], low++, mid++
19	After swap	(3, 6, 5)	[0, 0, 0, 1, 1, 1, 2, 2, 2]	Swapped arr[2] and arr[5]
20	mid=6 > high=5	(3, 6, 5)	[0, 0, 0, 1, 1, 1, 2, 2, 2]	Done

💡 Loop ends when mid (6) > high (5), array is partitioned into 0s, then 1s, then 2s.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	After Step 16	After Step 18	Final
low	0	0	0	1	1	1	2	2	2	3	3
mid	0	0	1	2	2	2	3	4	5	6	6
high	8	7	7	7	6	5	5	5	5	5	5

Key Moments - 3 Insights

Why do we swap arr[mid] with arr[high] when arr[mid] is 2 instead of moving mid forward?

Because the element swapped from arr[high] is unknown, we must check it again at arr[mid]. This is shown in steps 2-3 and 8-9 where mid stays the same after swapping.

Why do we increment both low and mid when arr[mid] is 0?

Because after swapping arr[low] and arr[mid], the element at mid is guaranteed to be processed (0), so we can safely move both pointers forward. See steps 6-7 and 12-13.

Why does the loop stop when mid > high?

Because all elements beyond high are 2s and already in place, and mid has scanned all elements up to high. This is shown in step 20.

Visual Quiz - 3 Questions

Look at the execution table at Step 6, what are the values of low, mid, and high?

A (0, 2, 7)

B (1, 1, 7)

C (0, 1, 7)

D (1, 2, 7)

💡 Hint

Check the 'Pointers (low, mid, high)' column at Step 6 in the execution table.

At which step does the condition mid <= high become false?

A Step 20

B Step 19

C Step 18

D Step 17

💡 Hint

Look at the exit note and the pointers at Step 20 in the execution table.

If we changed the first element from 2 to 0, how would the array state change at Step 3?

A No swap would happen, array stays the same

B low and mid would both increment

C mid would increment without swap

D Swap would happen with arr[high], array changes

💡 Hint

Recall that when arr[mid] is 0, we swap arr[low] and arr[mid] and increment both low and mid.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- mid scans array, swaps 0s to front (low), 2s to end (high)
- Increment pointers accordingly:
  * If 0: swap arr[low], arr[mid], low++, mid++
  * If 1: mid++
  * If 2: swap arr[mid], arr[high], high--
- Stop when mid > high
- Result: all 0s, then 1s, then 2s in order

Full Transcript

This visualization shows the Dutch National Flag three way partition algorithm. We start with three pointers: low, mid, and high. Initially, low and mid point to the start of the array, and high points to the end. We check the element at mid. If it is 0, we swap it with the element at low, then move both low and mid forward. If it is 1, we just move mid forward. If it is 2, we swap it with the element at high and move high backward, but keep mid at the same position to check the swapped element. We repeat this until mid passes high. The execution table traces each step, showing pointer positions, array state, and actions. The variable tracker shows how pointers change over time. Key moments clarify why we swap with high for 2s and why we increment pointers differently for 0s and 1s. The quiz tests understanding of pointer values and loop termination. This method efficiently sorts the array into three parts in one pass.

Practice

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

easy

A. To reverse the elements of an array

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

C. To find the maximum element in an array

D. To sort an array in ascending order

Solution

1. Step 1: Understand the algorithm's purpose

   The Dutch National Flag algorithm divides an array into three parts: elements 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 B

4. Quick Check:

   Partitioning by pivot = D [OK]

Hint: Remember: It partitions 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 Java syntax to swap two elements arr[i] and arr[j] in an integer array?

easy

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

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

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

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

Solution

1. Step 1: Understand swapping logic

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

2. Step 2: Check each option

   swap(arr[i], arr[j]); assumes a non-existent swap function; arr[i] = arr[j]; arr[j] = arr[i]; overwrites arr[i] without saving; int temp = arr[i]; arr[i] = arr[j]; arr[j] = arr[i]; loses original arr[i] value by assigning arr[j] = arr[i] after changing arr[i]; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; correctly uses temp.

3. Final Answer:

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

4. Quick Check:

   Use temp variable for swap = C [OK]

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

Common Mistakes:

• Overwriting one element before saving it
• Using a non-existent swap function
• Swapping without a temporary variable

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

medium

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

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

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

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

Solution

1. Step 1: Partition array by 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

   So the array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

   Partitioned array = A [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 Java 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. The pivot comparison should use > instead of <

B. The loop condition should be mid < high

C. swap function is called incorrectly with array elements instead of indices

D. The variables low, mid, high are not initialized properly

Solution

1. Step 1: Check swap function usage

   swap(arr[low], arr[mid]) passes values, not indices; swap needs indices to swap elements in array.

2. Step 2: Verify other parts

   Loop condition and variable initialization are correct; pivot comparisons are standard.

3. Final Answer:

   swap function is called incorrectly with array elements instead of indices -> Option C

4. Quick Check:

   Swap needs indices, not values = A [OK]

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

Common Mistakes:

• Passing values instead of indices to swap
• Wrong loop boundary condition
• Incorrect pivot comparison operators

5. Given an array arr = [3, 5, 2, 1, 4, 3, 2] and pivot = 3, how many swaps will the Dutch National Flag algorithm perform to partition the array?

hard

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Trace swaps during partition

   Initial: low=0, mid=0, high=6 - mid=0 (3 == pivot): mid++ (0 swaps) - mid=1 (5 > pivot): swap arr[mid] and arr[high] -> swap arr[1] and arr[6] (swap 1), high--=5 - mid=1 (now 2 < pivot): swap arr[low] and arr[mid] -> swap arr[0] and arr[1] (swap 2), low++=1, mid++=2 - mid=2 (2 < pivot): swap arr[low] and arr[mid] -> swap arr[1] and arr[2] (swap 3), low++=2, mid++=3 - mid=3 (1 < pivot): swap arr[low] and arr[mid] -> swap arr[2] and arr[3] (swap 4), low++=3, mid++=4 - mid=4 (4 > pivot): swap arr[mid] and arr[high] -> swap arr[4] and arr[5] (swap 5), high--=4 - mid=4 (now 3 == pivot): mid++=5 Loop ends as mid > high.

2. Step 2: Count total swaps

   Total swaps counted = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Count swaps carefully during partition = B [OK]

Hint: Count swaps when elements move across low, mid, high pointers [OK]

Common Mistakes:

• Counting swaps incorrectly when pivot equals element
• Ignoring swaps after high pointer moves
• Assuming one swap per iteration