Sort Colors Two Pointer Dutch Flag in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the left pointer at the start of the array.

DSA Go

left := [1]

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dlen(nums)

Attempts:

3 left

💡 Hint

Common Mistakes

Starting left pointer at 1 or -1 causes skipping the first element.

Setting left to len(nums) causes out-of-range errors.

The left pointer should start at index 0 to begin sorting from the start.

2fill in blank

medium

Complete the code to swap elements at indices left and current.

DSA Go

nums[[1]], nums[current] = nums[current], nums[[1]]

Drag options to blanks, or click blank then click option'

Aright

B0

Ccurrent

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with right pointer instead of left.

Swapping current with itself does nothing.

We swap the element at left with the element at current to move 0s to the front.

3fill in blank

hard

Fix the error in the loop condition to continue while current is less than or equal to right.

DSA Go

for current [1] right {

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '>=' causes the loop to never run or run incorrectly.

Using '<' misses the last element at right.

The loop should run while current is less than or equal to right to process all elements.

4fill in blank

hard

Fill both blanks to correctly update pointers after swapping a 0.

DSA Go

nums[[1]], nums[current] = nums[current], nums[[1]]
left[2]

Drag options to blanks, or click blank then click option'

Aleft

Bright

Ccurrent

D+= 1

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing right instead of left after swapping 0.

Not incrementing any pointer causes infinite loop.

After swapping with left, increment left to move boundary forward.

5fill in blank

hard

Fill all three blanks to correctly swap with right pointer and update pointers after encountering a 2.

DSA Go

nums[[1]], nums[current] = nums[current], nums[[1]]
right[2]
[3]

Drag options to blanks, or click blank then click option'

Aleft

Bright

C-= 1

Dcurrent += 1

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing right instead of decrementing.

Not moving current pointer after swap causes infinite loop.

Swap with right, decrement right, and increment current to continue sorting.

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