Sort Colors Two Pointer Dutch Flag in DSA Go

Mental Model

We use three pointers to separate the array into three parts by swapping colors in one pass.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls between boxes using two hands and one helper hand.

Index:  0   1   2   3   4   5   6
Array: [2] [0] [2] [1] [1] [0] [0]
Pointers:
low ↑          
mid ↑          
high           ↑

Dry Run Walkthrough

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

Goal: Sort the array so that all 0s come first, then 1s, then 2s

Step 1: mid points at index 0 with value 2, swap with high at index 6

[0] [0] [2] [1] [1] [0] [2]
low ↑ mid ↑                 high ↑

Why: We move 2 to the end to group all 2s at the right

Step 2: mid points at index 0 with value 0, swap with low at index 0, move low and mid forward

[0] [0] [2] [1] [1] [0] [2]
     low ↑ mid ↑           high ↑

Why: 0 belongs at the start, so swap with low and move pointers

Step 3: mid points at index 1 with value 0, swap with low at index 1, move low and mid forward

[0] [0] [2] [1] [1] [0] [2]
          low ↑ mid ↑      high ↑

Why: Another 0 found, swap with low to keep 0s at front

Step 4: mid points at index 2 with value 2, swap with high at index 5

[0] [0] [0] [1] [1] [2] [2]
          low ↑ mid ↑      high ↑

Why: Move 2 to the end to group all 2s

Step 5: mid points at index 2 with value 0, swap with low at index 2, move low and mid forward

[0] [0] [0] [1] [1] [2] [2]
               low ↑ mid ↑ high ↑

Why: 0 belongs at start, swap and move pointers

Step 6: mid points at index 3 with value 1, just move mid forward

[0] [0] [0] [1] [1] [2] [2]
               low ↑     mid ↑ high ↑

Why: 1 is in the middle, no swap needed, just move mid

Step 7: mid points at index 4 with value 1, just move mid forward

[0] [0] [0] [1] [1] [2] [2]
               low ↑         mid ↑ high ↑

Why: 1 is in the middle, move mid forward

Result:

[0] -> [0] -> [0] -> [1] -> [1] -> [2] -> [2] -> null

Annotated Code

DSA Go

package main

import "fmt"

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

func printArray(nums []int) {
    for i, v := range nums {
        if i > 0 {
            fmt.Print(" -> ")
        }
        fmt.Print(v)
    }
    fmt.Println(" -> null")
}

func main() {
    nums := []int{2, 0, 2, 1, 1, 0, 0}
    sortColors(nums)
    printArray(nums)
}

for mid <= high {

loop until mid passes high to process all elements

if nums[mid] == 0 {

if current is 0, swap with low to move 0s to front

nums[low], nums[mid] = nums[mid], nums[low]

swap 0 at mid with element at low

low++ mid++

increment low and mid to move forward

else if nums[mid] == 1 {

if current is 1, just move mid forward

mid++

advance mid pointer

else { // nums[mid] == 2

if current is 2, swap with high to move 2s to end

nums[mid], nums[high] = nums[high], nums[mid]

swap 2 at mid with element at high

high--

decrement high to shrink the unsorted region from right

Output

0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer

Space: O(1) because sorting is done in place without extra space

vs Alternative: Compared to counting sort which needs extra space and two passes, this uses one pass and no extra space

Edge Cases

empty array

function completes immediately without error

DSA Go

for mid <= high {

array with all zeros

all elements remain zeros, pointers move through array

DSA Go

if nums[mid] == 0 {

array with all twos

all elements remain twos, swapped with themselves, high pointer moves down

DSA Go

else { // nums[mid] == 2

When to Use This Pattern

When you need to sort an array with three distinct values quickly, use the Dutch National Flag pattern with two pointers to partition in one pass.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high when nums[mid] == 2
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Summary

Sorts an array of 0s, 1s, and 2s in one pass using three pointers.

Use when you have exactly three categories to sort efficiently without extra space.

The key is to keep three regions and swap elements to their correct region while scanning once.

Practice

1. What is the main idea behind the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. Use three pointers to separate 0s, 1s, and 2s in one pass

B. Sort the array using bubble sort repeatedly

C. Count each color and then overwrite the array

D. Use recursion to sort colors

Solution

1. Step 1: Understand the problem

   The algorithm sorts an array containing only 0s, 1s, and 2s representing colors.

2. Step 2: Identify the approach

   It uses three pointers (low, mid, high) to place 0s at the start, 2s at the end, and 1s in the middle in one pass.

3. Final Answer:

   Use three pointers to separate 0s, 1s, and 2s in one pass -> Option A

4. Quick Check:

   Three pointers = One pass sorting [OK]

Hint: Remember three pointers separate colors in one pass [OK]

Common Mistakes:

• Thinking it uses multiple passes like bubble sort
• Confusing counting approach with two-pointer method
• Assuming recursion is used

2. Which of the following Go code snippets correctly initializes the three pointers for the Dutch Flag algorithm?

easy

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

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

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

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

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high starts at last index (len(nums)-1).

2. Step 2: Match initialization

   low, mid, high := 0, 0, len(nums)-1 correctly sets low=0, mid=0, high=len(nums)-1.

3. Final Answer:

   low, mid, high := 0, 0, len(nums)-1 -> Option A

4. Quick Check:

   Pointers start at array ends and start [OK]

Hint: Start low and mid at 0, high at last index [OK]

Common Mistakes:

• Swapping low and high initialization
• Setting pointers outside array bounds
• Confusing mid pointer position

3. What will be the output of the following Go code after applying the Dutch Flag algorithm?

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

medium

A. [0 1 0 1 2 2]

B. [0 0 1 1 2 2]

C. [2 2 1 1 0 0]

D. [1 1 0 0 2 2]

Solution

1. Step 1: Trace the loop iterations

   Initially nums = [2,0,2,1,1,0], low=0, mid=0, high=5. The loop swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After processing, nums becomes [0,0,1,1,2,2].

3. Final Answer:

   [0 0 1 1 2 2] -> Option B

4. Quick Check:

   Sorted colors = [0 0 1 1 2 2] [OK]

Hint: Swap 0s left, 2s right, 1s stay middle [OK]

Common Mistakes:

• Not updating mid after swapping 0
• Updating mid after swapping 2 incorrectly
• Confusing order of swaps

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

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

medium

A. Swapping 0s and 2s is done in wrong order

B. Pointers low and mid are initialized incorrectly

C. Loop condition should be mid <= high, not mid < high

D. The array is not initialized properly

Solution

1. Step 1: Check loop condition

   The loop uses 'mid < high' but it should be 'mid <= high' to process all elements including when mid equals high.

2. Step 2: Effect of wrong condition

   With 'mid < high', the last element may not be processed, causing incorrect sorting.

3. Final Answer:

   Loop condition should be mid <= high, not mid < high -> Option C

4. Quick Check:

   Loop must cover all elements [OK]

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

Common Mistakes:

• Using mid < high misses last element
• Incorrect pointer initialization
• Swapping logic errors

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

hard

A. Count swaps after sorting by comparing original and sorted arrays

B. Swaps cannot be counted in this algorithm

C. Use recursion to count swaps automatically

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

Solution

1. Step 1: Understand swap points

   Swaps happen when 0s or 2s are moved by exchanging elements inside the loop.

2. Step 2: Implement swap counter

   Introduce a variable initialized to 0 before the loop and increment it each time a swap statement executes.

3. Final Answer:

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

4. Quick Check:

   Count swaps during execution [OK]

Hint: Increment counter on every swap inside loop [OK]

Common Mistakes:

• Counting swaps after sorting by comparing arrays
• Thinking recursion counts swaps automatically
• Assuming swaps cannot be tracked