Dutch National Flag Three Way Partition in DSA Go

Mental Model

We divide an array into three parts by moving elements less than, equal to, and greater than a pivot value into separate sections in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick each ball once and put it in the correct bin without mixing them up again.

Array: [2, 0, 2, 1, 1, 0]
Partitions: < pivot | = pivot | > pivot
Indexes:  low ↑  mid ↑  high ↓

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0], pivot = 1

Goal: Rearrange array so all 0s come first, then 1s, then 2s

Step 1: Start with low=0, mid=0, high=5

[2, 0, 2, 1, 1, 0]
low=0 ↑ mid=0 ↑ high=5 ↓

Why: Initialize pointers to track partitions

Step 2: Check mid=0 value 2 > pivot, swap with high=5 value 0, decrement high

[0, 0, 2, 1, 1, 2]
low=0 ↑ mid=0 ↑ high=4 ↓

Why: Move larger element to right partition

Step 3: Check mid=0 value 0 < pivot, swap with low=0 value 0, increment low and mid

[0, 0, 2, 1, 1, 2]
low=1 ↑ mid=1 ↑ high=4 ↓

Why: Move smaller element to left partition

Step 4: Check mid=1 value 0 < pivot, swap with low=1 value 0, increment low and mid

[0, 0, 2, 1, 1, 2]
low=2 ↑ mid=2 ↑ high=4 ↓

Why: Continue moving smaller elements left

Step 5: Check mid=2 value 2 > pivot, swap with high=4 value 1, decrement high

[0, 0, 1, 1, 2, 2]
low=2 ↑ mid=2 ↑ high=3 ↓

Why: Move larger element to right partition

Step 6: Check mid=2 value 1 == pivot, increment mid

[0, 0, 1, 1, 2, 2]
low=2 ↑ mid=3 ↑ high=3 ↓

Why: Keep equal elements in middle partition

Step 7: Check mid=3 value 1 == pivot, increment mid

[0, 0, 1, 1, 2, 2]
low=2 ↑ mid=4 ↑ high=3 ↓

Why: All elements processed, mid crossed high

Result:

[0, 0, 1, 1, 2, 2]
Final partition: < pivot | = pivot | > pivot

Annotated Code

DSA Go

package main

import "fmt"

func dutchNationalFlag(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] > pivot
            arr[mid], arr[high] = arr[high], arr[mid]
            high--
        }
    }
}

func main() {
    arr := []int{2, 0, 2, 1, 1, 0}
    pivot := 1
    dutchNationalFlag(arr, pivot)
    for i, v := range arr {
        if i == len(arr)-1 {
            fmt.Printf("%d\n", v)
        } else {
            fmt.Printf("%d, ", v)
        }
    }
}

for mid <= high {

loop until mid pointer passes high pointer

if arr[mid] < pivot {

if current element less than pivot, swap to left partition

arr[low], arr[mid] = arr[mid], arr[low]

swap element at mid with element at low

low++

expand left partition boundary

mid++

move mid pointer forward to process next element

} else if arr[mid] == pivot {

if element equals pivot, just move mid forward

mid++

keep equal elements in middle partition

} else {

if element greater than pivot, swap to right partition

arr[mid], arr[high] = arr[high], arr[mid]

swap element at mid with element at high

high--

reduce right partition boundary

Output

0, 0, 1, 1, 2, 2

Complexity Analysis

Time: O(n) because we scan the array once with three pointers moving forward or backward

Space: O(1) because the partitioning is done in place without extra storage

vs Alternative: Compared to sorting the array fully (O(n log n)), this approach is faster and simpler for three distinct groups

Edge Cases

empty array

function completes immediately without changes

DSA Go

for mid <= high {

all elements equal to pivot

mid pointer moves through all elements without swaps

DSA Go

else if arr[mid] == pivot {

no elements less than pivot

low pointer stays at 0, swaps only move larger elements right

DSA Go

if arr[mid] < pivot {

When to Use This Pattern

When you need to separate an array into three groups around a pivot in one pass, use the Dutch National Flag pattern for efficient partitioning.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high without checking the swapped element
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Summary

Rearranges an array into three parts: less than, equal to, and greater than a pivot value.

Use when you want to partition data into three groups efficiently in one pass.

The key is using three pointers to track boundaries and carefully swapping elements without missing any.

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