Dutch National Flag Three Way Partition in DSA Go - Build from Scratch

Dutch National Flag Three Way Partition

📖 Scenario: Imagine you have a list of colored balls represented by numbers: 0 for red, 1 for white, and 2 for blue. You want to arrange them so that all reds come first, then whites, and then blues, just like the Dutch flag.

🎯 Goal: You will write a Go program that rearranges a slice of integers containing 0s, 1s, and 2s so that all 0s come first, then all 1s, and finally all 2s.

📋 What You'll Learn

Create a slice called colors with the exact values []int{2, 0, 2, 1, 1, 0}

Create three integer variables low, mid, and high to help with partitioning

Implement the Dutch National Flag algorithm using a for loop and switch statement on colors[mid]

Print the final colors slice after partitioning

💡 Why This Matters

🌍 Real World

Sorting items into categories quickly is useful in many places, like organizing colored balls, sorting tasks by priority, or grouping data by type.

💼 Career

Understanding partitioning algorithms like Dutch National Flag helps in coding interviews and building efficient sorting and grouping functions in software development.

1

Create the initial slice of colors

Create a slice called colors with the exact values []int{2, 0, 2, 1, 1, 0}.

DSA Go

package main

import "fmt"

func main() {
    // Create the colors slice here
    // Your code here
}

Hint

Use colors := []int{2, 0, 2, 1, 1, 0} to create the slice.

2

Initialize pointers for partitioning

Create three integer variables called low, mid, and high. Set low and mid to 0, and high to len(colors) - 1.

DSA Go

package main

import "fmt"

func main() {
    colors := []int{2, 0, 2, 1, 1, 0}
    // Initialize low, mid, and high pointers
    // Your code here
}

Hint

Use low, mid := 0, 0 and high := len(colors) - 1.

3

Implement the Dutch National Flag partitioning logic

Use a for loop with the condition mid <= high. Inside the loop, use a switch on colors[mid]. If it is 0, swap colors[low] and colors[mid], then increment low and mid. If it is 1, just increment mid. If it is 2, swap colors[mid] and colors[high], then decrement high.

DSA Go

package main

import "fmt"

func main() {
    colors := []int{2, 0, 2, 1, 1, 0}
    low, mid := 0, 0
    high := len(colors) - 1

    // Implement the partitioning loop here
    // Your code here
}

Hint

Use a for mid <= high loop and a switch on colors[mid] with cases 0, 1, and 2.

4

Print the sorted colors slice

Print the colors slice using fmt.Println(colors).

DSA Go

package main

import "fmt"

func main() {
    colors := []int{2, 0, 2, 1, 1, 0}
    low, mid := 0, 0
    high := len(colors) - 1

    for mid <= high {
        switch colors[mid] {
        case 0:
            colors[low], colors[mid] = colors[mid], colors[low]
            low++
            mid++
        case 1:
            mid++
        case 2:
            colors[mid], colors[high] = colors[high], colors[mid]
            high--
        }
    }

    // Print the colors slice
    // Your code here
}

Hint

Use fmt.Println(colors) to print the final slice.

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