Sort Colors Two Pointer Dutch Flag in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Dutch National Flag problem?

It is to sort an array containing three different values (like 0, 1, 2) in a single pass using pointers, without extra space.

beginner

In the Dutch Flag algorithm, what do the three pointers represent?

They represent boundaries: low for 0s, mid for current element, and high for 2s.

intermediate

Why does the Dutch Flag algorithm only need one pass through the array?

Because it swaps elements in place and moves pointers to ensure each element is checked once.

intermediate

What happens when the mid pointer encounters a 0 in the Dutch Flag algorithm?

Swap the element at mid with the element at low, then move both low and mid pointers forward.

intermediate

How does the algorithm handle encountering a 2 at the mid pointer?

Swap the element at mid with the element at high, then move the high pointer backward without moving mid.

What does the 'low' pointer represent in the Dutch Flag algorithm?

A Boundary for 0s

B Boundary for 1s

C Boundary for 2s

D Current element

The 'low' pointer marks the boundary where all elements before it are 0s.

When the mid pointer points to a 1, what should the algorithm do?

A Stop the algorithm

B Swap with high pointer and move high

C Swap with low pointer and move both

D Just move mid pointer forward

When mid points to 1, just move mid forward because 1s are in the middle.

Why does the algorithm not move the mid pointer after swapping with high pointer?

A Because mid is always at the end

B Because the swapped element needs to be checked

C Because high pointer is invalid

D Because low pointer moves instead

After swapping with high, the element at mid might be 0,1 or 2, so it needs checking.

What is the time complexity of the Dutch Flag algorithm?

A O(n)

B O(n log n)

C O(n^2)

D O(1)

The algorithm runs in linear time, O(n), because it processes each element once.

Which of these is NOT true about the Dutch Flag algorithm?

A It sorts colors in one pass

B It uses three pointers

C It uses extra space proportional to input size

D It swaps elements in place

The algorithm sorts in place and uses constant extra space, not proportional to input size.

Explain how the two-pointer Dutch Flag algorithm sorts an array of 0s, 1s, and 2s.

Think about how each pointer moves and what happens when mid sees 0, 1, or 2.

Describe the role of each pointer in the Dutch Flag problem and how they help achieve sorting.

Focus on how pointers divide the array into sorted and unsorted parts.

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