Sort Colors Two Pointer Dutch Flag in DSA Go - Build from Scratch

Sort Colors Using Two Pointer Dutch Flag Algorithm

📖 Scenario: You are organizing colored balls in a row. Each ball is either red, white, or blue. You want to arrange them so that all red balls come first, then white balls, and finally blue balls.

🎯 Goal: Build a program that sorts a list of colors represented by numbers 0 (red), 1 (white), and 2 (blue) using the two-pointer Dutch Flag algorithm.

📋 What You'll Learn

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

Create two integer variables low and high to track positions

Use a for loop with an index variable i to iterate through colors

Implement the two-pointer Dutch Flag sorting logic inside the loop

Print the sorted colors slice at the end

💡 Why This Matters

🌍 Real World

Sorting colored items quickly is useful in games, graphics, and organizing data visually.

💼 Career

Understanding two-pointer techniques and in-place sorting is valuable for coding interviews and efficient software development.

1

Create the initial colors slice

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

DSA Go

# Create the colors slice with the given values
# Your code here

Hint

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

2

Add two pointer variables low and high

Add two integer variables called low set to 0 and high set to len(colors) - 1.

DSA Go

package main

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

Hint

Use low := 0 and high := len(colors) - 1 to set the pointers.

3

Implement the two-pointer Dutch Flag sorting logic

Use a for loop with variable i starting at 0 and running while i <= high. Inside the loop, apply the Dutch Flag logic: if colors[i] == 0, swap with colors[low] and increment low and i; if colors[i] == 2, swap with colors[high] and decrement high; else increment i.

DSA Go

package main

func main() {
    colors := []int{2, 0, 2, 1, 1, 0}
    low := 0
    high := len(colors) - 1
    // Implement the Dutch Flag sorting logic here
    // Your code here
}

Hint

Use a for loop with i and apply swaps and pointer moves as per the Dutch Flag algorithm.

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 := 0
    high := len(colors) - 1
    i := 0
    for i <= high {
        if colors[i] == 0 {
            colors[i], colors[low] = colors[low], colors[i]
            low++
            i++
        } else if colors[i] == 2 {
            colors[i], colors[high] = colors[high], colors[i]
            high--
        } else {
            i++
        }
    }
    // Print the sorted colors slice
    // Your code here
}

Hint

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

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