Dutch National Flag Three Way Partition in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the low pointer to start the partition.

DSA Go

low := [1]

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dlen(arr)

Attempts:

3 left

💡 Hint

Common Mistakes

Starting low at 1 or -1 causes index errors.

Using length of array as start.

The low pointer starts at index 0 to track the boundary of elements less than the pivot.

2fill in blank

medium

Complete the code to swap elements at indices i and low.

DSA Go

arr[i], arr[[1]] = arr[[1]], arr[i]

Drag options to blanks, or click blank then click option'

Amid

Blow

Chigh

Dpivot

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with high or mid causes incorrect partition.

Swapping with pivot index is invalid.

We swap the current element at i with the element at low to move smaller elements to the front.

3fill in blank

hard

Fix the error in the loop condition to correctly iterate over the array.

DSA Go

for i := 0; i [1] high; {

Drag options to blanks, or click blank then click option'

A>

B>=

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' causes no iteration.

Using '>' skips elements.

Using '<=' causes out of bounds.

The loop should run while i is less than high to process all elements before the high pointer.

4fill in blank

hard

Fill both blanks to correctly update pointers after swapping with high.

DSA Go

arr[i], arr[[1]] = arr[[1]], arr[i]
high[2]

Drag options to blanks, or click blank then click option'

Ahigh

Blow

C--

D++

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing high instead of decrementing.

Using low pointer incorrectly here.

After swapping with high, decrement high to shrink the upper partition.

5fill in blank

hard

Fill all three blanks to complete the partition loop with correct pointer updates.

DSA Go

for i := 0; i [1] high; {
    if arr[i] < pivot {
        arr[i], arr[[2]] = arr[[2]], arr[i]
        [3]++
        i++
    } else if arr[i] > pivot {
        arr[i], arr[high] = arr[high], arr[i]
        high--
    } else {
        i++
    }
}

Drag options to blanks, or click blank then click option'

A<=

Blow

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes off-by-one errors.

Incrementing wrong pointer after swap.

The loop runs while i < high. Swap with low pointer and increment low after swap.

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