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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on Array

What is the output of the following Go code that performs the Dutch National Flag partition on the array?

DSA Go

package main
import "fmt"

func dutchFlagPartition(arr []int, pivot int) {
    low, mid, high := 0, 0, len(arr)-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--
        }
    }
}

func main() {
    arr := []int{2, 0, 2, 1, 1, 0}
    dutchFlagPartition(arr, 1)
    fmt.Println(arr)
}

A [1 1 0 0 2 2]

B [0 0 1 1 2 2]

C [0 1 0 1 2 2]

D [2 2 1 1 0 0]

💡 Hint

Focus on how the pointers low, mid, and high move and swap elements based on comparison with pivot.

The algorithm partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. After processing, all 0s come first, then 1s, then 2s.

🧠 Conceptual

intermediate

Understanding Pointers in Dutch National Flag Algorithm

In the Dutch National Flag algorithm, what is the role of the 'mid' pointer during the partitioning process?

A It scans through the array to examine each element and decide its position.

B It marks the boundary between elements less than pivot and equal to pivot.

C It points to the last element greater than the pivot.

D It keeps track of the number of elements equal to the pivot.

💡 Hint

Think about which pointer moves forward to check elements one by one.

The 'mid' pointer moves through the array from start to end, examining each element to decide if it should be swapped to the front, left as is, or swapped to the end.

🔧 Debug

advanced

Identify the Bug in Dutch National Flag Implementation

What error will occur when running this Go code for Dutch National Flag partition?

DSA Go

package main
import "fmt"

func dutchFlagPartition(arr []int, pivot int) {
    low, mid, high := 0, 0, len(arr)
    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--
        }
    }
}

func main() {
    arr := []int{2, 0, 2, 1, 1, 0}
    dutchFlagPartition(arr, 1)
    fmt.Println(arr)
}

A logic error: array remains unsorted

B compilation error: missing import

C no error, outputs [0 0 1 1 2 2]

D runtime error: index out of range

💡 Hint

Check the initialization of 'high' and how it is used as an index.

The 'high' pointer is initialized to len(arr), which is out of bounds for indexing. Accessing arr[high] causes a runtime panic.

🚀 Application

advanced

Using Dutch National Flag to Sort Colors

Given an array representing colors as 0 (red), 1 (white), and 2 (blue), which option correctly sorts the array using Dutch National Flag algorithm?

DSA Go

func sortColors(nums []int) {
    low, mid, high := 0, 0, len(nums)-1
    for mid <= high {
        switch {
        case nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low++
            mid++
        case nums[mid] == 1:
            mid++
        case nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

A Sorts array so all 0s, then 1s, then 2s appear in order

B Sorts array so all 2s, then 1s, then 0s appear in order

C Sorts array but 1s appear before 0s

D Does not sort array, leaves it unchanged

💡 Hint

Check how the swaps and pointer movements organize the colors.

The algorithm moves all 0s to the front, 2s to the end, and 1s remain in the middle, sorting the colors correctly.

🧠 Conceptual

expert

Time Complexity of Dutch National Flag Algorithm

What is the time complexity of the Dutch National Flag algorithm for partitioning an array of size n?

A O(n^2) because of nested loops

B O(n log n) due to recursive partitioning

C O(n) because each element is visited at most once

D O(log n) because it divides the array in halves

💡 Hint

Consider how many times each element is processed during the partition.

The algorithm uses three pointers and processes each element once, resulting in linear time complexity O(n).

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