Sort Colors Two Pointer Dutch Flag in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch Flag Algorithm After One Pass

What is the state of the array after the first pass of the Dutch National Flag algorithm on the input array?

DSA Go

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], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

nums := []int{2, 0, 2, 1, 1, 0}
sortColors(nums)
fmt.Println(nums)

A [2, 0, 0, 1, 1, 2]

B [0, 0, 2, 1, 1, 2]

C [0, 0, 1, 2, 1, 2]

D [0, 0, 1, 1, 2, 2]

💡 Hint

Think about how the pointers low, mid, and high move and swap elements.

The Dutch National Flag algorithm sorts the array in one pass by moving 0s to the front, 2s to the end, and 1s stay in the middle. After the full pass, the array is sorted as [0, 0, 1, 1, 2, 2].

🧠 Conceptual

intermediate

Why Use Three Pointers in Dutch Flag Algorithm?

Why does the Dutch National Flag algorithm use three pointers (low, mid, high) instead of just one or two?

A To count the number of 0s, 1s, and 2s before sorting.

B To separate the array into three parts: 0s, 1s, and 2s efficiently in one pass.

C To sort the array twice for better accuracy.

D To use extra memory for temporary storage of elements.

💡 Hint

Think about how the algorithm divides the array during sorting.

The three pointers help partition the array into three sections: all 0s before low, all 1s between low and mid, and all 2s after high, allowing sorting in one pass without extra space.

🔧 Debug

advanced

Identify the Bug in This Dutch Flag Implementation

What error will this code produce when sorting colors using the Dutch National Flag algorithm?

DSA Go

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], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

A The loop condition 'mid < high' causes some elements to be skipped, resulting in incorrect sorting.

B The code will cause an index out of range error.

C The code will run infinitely because pointers never move.

D The code will sort correctly without any error.

💡 Hint

Check the loop condition carefully and think about when the loop stops.

The loop should run while mid <= high to ensure all elements are processed. Using mid < high skips checking the element at index high, causing incorrect sorting.

❓ Predict Output

advanced

Final Array After Partial Dutch Flag Execution

Given the array and the Dutch National Flag algorithm, what is the array state after the first swap operation?

DSA Go

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

A [1, 2, 0, 1, 2, 0]

B [0, 2, 1, 1, 2, 0]

C [1, 0, 2, 1, 2, 0]

D ]0 ,2 ,1 ,0 ,2 ,1[

💡 Hint

Check the value at nums[mid] before the swap.

Since nums[mid] is 1, the code only increments mid without swapping, so the array remains unchanged.

🚀 Application

expert

Number of Swaps in Dutch National Flag Algorithm

For the input array [2, 0, 2, 1, 1, 0], how many swaps does the Dutch National Flag algorithm perform to sort the array?

A 5

B 3

C 4

D 6

💡 Hint

Trace the swaps carefully during the sorting process.

The algorithm swaps elements when moving 0s to the front and 2s to the end. For this input, it performs exactly 4 swaps.

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