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

Concept Flow - Dutch National Flag Three Way Partition

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

↓

Check mid <= high?

No→Done

Yes↓

Check arr[mid

↓

Swap arr[low

↓

Swap arr[mid

↩Back to check mid <= high?

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

Execution Sample

DSA Go

arr := []int{2, 0, 2, 1, 1, 0}
low, mid, high := 0, 0, len(arr)-1
pivot := 1
for mid <= high {
  if arr[mid] < pivot { /* swap and move low, mid */ }
  else if arr[mid] > pivot { /* swap and move high */ }
  else { mid++ }
}

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

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2, 0, 2, 1, 1, 0]	Initial pointers
2	Check arr[mid]=2 > pivot=1	0	0	5	[2, 0, 2, 1, 1, 0]	Swap arr[mid] and arr[high], high--
3	Swap arr[0]<->arr[5]	0	0	4	[0, 0, 2, 1, 1, 2]	high=4, mid=0 (mid not incremented)
4	Check arr[mid]=0 < pivot=1	0	0	4	[0, 0, 2, 1, 1, 2]	Swap arr[low] and arr[mid], low++, mid++
5	Swap arr[0]<->arr[0]	1	1	4	[0, 0, 2, 1, 1, 2]	low=1, mid=1
6	Check arr[mid]=0 < pivot=1	1	1	4	[0, 0, 2, 1, 1, 2]	Swap arr[low] and arr[mid], low++, mid++
7	Swap arr[1]<->arr[1]	2	2	4	[0, 0, 2, 1, 1, 2]	low=2, mid=2
8	Check arr[mid]=2 > pivot=1	2	2	4	[0, 0, 2, 1, 1, 2]	Swap arr[mid] and arr[high], high--
9	Swap arr[2]<->arr[4]	2	2	3	[0, 0, 1, 1, 2, 2]	high=3, mid=2 (mid not incremented)
10	Check arr[mid]=1 == pivot=1	2	2	3	[0, 0, 1, 1, 2, 2]	mid++
11	mid=3 <= high=3, Check arr[mid]=1 == pivot=1	2	3	3	[0, 0, 1, 1, 2, 2]	mid++
12	mid=4 > high=3, End	2	4	3	[0, 0, 1, 1, 2, 2]	Done

💡 mid (4) > high (3), partition complete

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
low	0	0	1	2	2	2	2
mid	0	0	1	2	2	4	4
high	5	4	4	4	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]

Key Moments - 3 Insights

Why do we not increment mid after swapping with high when arr[mid] > pivot?

Because after swapping with arr[high], the new element at mid is unprocessed. We must check it again, as shown in steps 2-3 and 8-9 in the execution_table.

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

Because swapping arr[low] and arr[mid] places a smaller element in the correct section, so both pointers move forward to process the next elements, as seen in steps 4-7.

What condition ends the partitioning loop?

The loop ends when mid passes high (mid > high), meaning all elements are partitioned, as shown in step 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the array state after the swap?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 9 in the execution_table.

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

A Step 4

B Step 2

C Step 10

D Step 8

💡 Hint

Look for the first step where operation is 'mid++' without swap in execution_table.

If the pivot was changed to 2, how would the pointer movement change at step 2?

A mid would increment because arr[mid] < pivot

B high would decrement because arr[mid] > pivot

C low and mid would increment because arr[mid] < pivot

D No swap or pointer change

💡 Hint

Compare arr[mid]=2 with pivot=2 and check pointer actions in execution_table step 2.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- Elements < pivot go before low
- Elements == pivot stay between low and high
- Elements > pivot go after high
- Swap and move pointers accordingly
- Loop ends when mid > high

Full Transcript

This visualization traces the Dutch National Flag algorithm that partitions an array into three parts based on a pivot value. We use three pointers: low, mid, and high. Starting with mid at 0 and high at the last index, we check the element at mid. If it is less than the pivot, we swap it with the element at low and move both low and mid forward. If it is greater than the pivot, we swap it with the element at high and move high backward without moving mid, because the swapped element needs checking. If it equals the pivot, we just move mid forward. This continues until mid passes high, ensuring the array is partitioned into three sections: less than, equal to, and greater than the pivot. The execution table shows each step with pointer positions and array state, helping understand how the algorithm rearranges elements in place.

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 sort an array in ascending order using quicksort

C. To find the maximum element in an array

D. To rearrange an array so that elements less than, equal to, and greater than a pivot are grouped separately

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Compare with other options

   The other options describe different operations: sorting, finding max, and reversing, which are not the main goal here.

3. Final Answer:

   To rearrange an array so that elements less than, equal to, and greater than a pivot are grouped separately -> Option D

4. Quick Check:

   Partitioning array by pivot = A [OK]

Hint: Remember: three groups around pivot, not full sorting [OK]

Common Mistakes:

• Confusing partition with full sorting
• Thinking it only separates two groups
• Assuming it finds max or min values

2. Which of the following Go code snippets correctly initializes the pointers for the Dutch National Flag algorithm on an array arr?

easy

A. low, mid, high := 0, len(arr), len(arr)-1

B. low, mid, high := 0, 0, len(arr)-1

C. low, mid, high := -1, 0, len(arr)

D. low, mid, high := 1, 1, len(arr)-1

Solution

1. Step 1: Identify correct pointer initialization

   In Dutch National Flag, low and mid start at 0, high at last index len(arr)-1.

2. Step 2: Check each option

   low, mid, high := 0, 0, len(arr)-1 matches this. low, mid, high := -1, 0, len(arr) uses invalid indices (-1 and len(arr)). low, mid, high := 0, len(arr), len(arr)-1 sets mid to len(arr) which is out of range. low, mid, high := 1, 1, len(arr)-1 starts pointers at 1, skipping first element.

3. Final Answer:

   low, mid, high := 0, 0, len(arr)-1 -> Option B

4. Quick Check:

   Correct pointer start = C [OK]

Hint: Pointers start at array ends: low=0, mid=0, high=last index [OK]

Common Mistakes:

• Setting mid or high out of array bounds
• Starting pointers at 1 instead of 0
• Using negative indices in Go arrays

3. What will be the output of the following Go code after applying the Dutch National Flag algorithm with pivot = 1?

arr := []int{2, 0, 1, 2, 1, 0}
low, mid, high := 0, 0, len(arr)-1
pivot := 1
for mid <= high {
  if arr[mid] < pivot {
    arr[low], arr[mid] = arr[mid], arr[low]
    low++
    mid++
  } else if arr[mid] == pivot {
    mid++
  } else {
    arr[mid], arr[high] = arr[high], arr[mid]
    high--
  }
}
fmt.Println(arr)

medium

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

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

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

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

Solution

1. Step 1: Trace the partition process

   Initial array: [2, 0, 1, 2, 1, 0]. Pivot = 1. The algorithm moves elements less than 1 to front, equal in middle, greater at end.

2. Step 2: Final array after partition

   After processing, array becomes [0, 0, 1, 1, 2, 2], grouping 0s, then 1s, then 2s.

3. Final Answer:

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

4. Quick Check:

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

Hint: Group less, equal, greater than pivot in one pass [OK]

Common Mistakes:

• Not swapping correctly when arr[mid] > pivot
• Incrementing mid incorrectly after swap
• Confusing pivot value with array elements

4. Identify the bug in this Go code snippet implementing Dutch National Flag partition:

arr := []int{1, 2, 0, 1, 2}
low, mid, high := 0, 0, len(arr)-1
pivot := 1
for mid < high {
  if arr[mid] < pivot {
    arr[low], arr[mid] = arr[mid], arr[low]
    low++
    mid++
  } else if arr[mid] == pivot {
    mid++
  } else {
    arr[mid], arr[high] = arr[high], arr[mid]
    high--
  }
}
fmt.Println(arr)

medium

A. The pivot value is incorrect

B. Pointers low and mid are initialized incorrectly

C. The loop condition should be 'mid <= high' instead of 'mid < high'

D. Swapping elements is done in wrong order

Solution

1. Step 1: Analyze loop condition

   The loop uses 'mid < high', which misses processing when mid equals high. It should be 'mid <= high' to cover all elements.

2. Step 2: Check other parts

   Pivot is correct, pointers initialized properly, and swapping order is correct. Only loop condition is wrong.

3. Final Answer:

   The loop condition should be 'mid <= high' instead of 'mid < high' -> Option C

4. Quick Check:

   Loop must cover mid = high index [OK]

Hint: Use 'mid <= high' to process all elements including last [OK]

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pivot unnecessarily
• Incorrect pointer initialization

5. Given an array arr containing only 0s, 1s, and 2s, how can you modify the Dutch National Flag algorithm to count the number of swaps performed during partitioning?

medium

A. Add a swap counter variable and increment it each time a swap occurs inside the loop

B. Count swaps only when elements are equal to the pivot

C. Increment counter only when mid pointer moves forward

D. Use a separate loop after partition to count swaps

Solution

1. Step 1: Understand swap counting

   Swaps happen when elements are exchanged. To count them, add a variable initialized to zero before the loop.

2. Step 2: Increment counter on each swap

   Inside the loop, whenever a swap occurs (either arr[low], arr[mid] or arr[mid], arr[high]), increment the counter by one.

3. Final Answer:

   Add a swap counter variable and increment it each time a swap occurs inside the loop -> Option A

4. Quick Check:

   Count swaps during actual swaps [OK]

Hint: Increment counter exactly when swapping elements [OK]

Common Mistakes:

• Counting swaps only for pivot equals
• Counting pointer moves instead of swaps
• Using separate loop to count swaps after partition