Sort Colors Two Pointer Dutch Flag in DSA Python - 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 two-pointer Dutch Flag algorithm, what do the pointers low, mid, and high represent?

Low points to the boundary of 0s, mid is the current element under consideration, and high points to the boundary of 2s.

intermediate

Why do we swap elements when nums[mid] is 0 or 2 in the Dutch Flag algorithm?

Because 0s should be moved to the front (low side) and 2s to the end (high side), swapping places them correctly while mid moves forward or stays to check the swapped element.

beginner

What happens when nums[mid] is 1 in the Dutch Flag algorithm?

We simply move mid forward because 1s belong in the middle and are already in the correct place.

beginner

What is the time complexity of the Dutch National Flag sorting algorithm?

It is O(n) because it makes a single pass through the array with constant time operations.

In the Dutch Flag problem, which pointer moves forward when nums[mid] == 0?

A High pointer moves backward

B Only mid pointer moves forward

C Only low pointer moves forward

D Both low and mid pointers move forward

When nums[mid] is 0, we swap with nums[low], then move both low and mid forward.

What should you do when nums[mid] == 2 in the Dutch Flag algorithm?

A Swap nums[mid] with nums[high] and move high backward

B Swap nums[mid] with nums[high] and move mid forward

C Move mid forward only

D Move low forward only

When nums[mid] is 2, swap with nums[high] and move high backward; mid stays to check the swapped element.

What is the initial position of the high pointer in the Dutch Flag algorithm?

A At the start of the array

B At the end of the array

C At the middle of the array

D One position after the end

High pointer starts at the last index of the array.

How many passes does the Dutch Flag algorithm make over the array?

A One pass

B Two passes

C Three passes

D Depends on array size

The algorithm sorts the array in a single pass.

Which of these is NOT a benefit of the Dutch Flag algorithm?

A In-place sorting

B Single pass solution

C Uses extra memory for sorting

D Linear time complexity

The algorithm does NOT use extra memory; it sorts in-place.

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

Think about how you separate colors by moving pointers and swapping.

Describe the role of each pointer (low, mid, high) in the Dutch Flag sorting algorithm.

Imagine dividing the array into three parts as you sort.

Practice

1. What is the main goal of the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. To reverse the elements of an array

B. To sort any array of integers in ascending order

C. To find the maximum element in an array

D. To sort an array containing only 0s, 1s, and 2s in a single pass

Solution

1. Step 1: Understand the problem context

   The algorithm is designed specifically for arrays with only three distinct values: 0, 1, and 2.

2. Step 2: Identify the algorithm's purpose

   It sorts these values in one pass using two pointers, placing all 0s first, then 1s, then 2s.

3. Final Answer:

   To sort an array containing only 0s, 1s, and 2s in a single pass -> Option D

4. Quick Check:

   Sort colors = sort 0,1,2 in one pass [OK]

Hint: Remember: Dutch Flag sorts 0,1,2 in one pass [OK]

Common Mistakes:

• Thinking it sorts any array, not just 0,1,2
• Confusing it with general sorting algorithms
• Assuming it requires multiple passes

2. Which of the following is the correct initialization of pointers in the Dutch Flag algorithm in Python?

easy

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

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

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

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

Solution

1. Step 1: Recall pointer roles

   Low and mid start at the beginning (index 0), high starts at the end (last index).

2. Step 2: Match initialization

   So, low = 0, mid = 0, high = len(nums) - 1 is correct.

3. Final Answer:

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

4. Quick Check:

   Pointers start low=0, mid=0, high=end [OK]

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

Common Mistakes:

• Swapping high and mid initialization
• Starting pointers at wrong indices
• Using length instead of length-1 for high

3. What will be the output of the following code snippet?

nums = [2, 0, 2, 1, 1, 0]
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

medium

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

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

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

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

Solution

1. Step 1: Trace the algorithm on input

   Initially nums = [2,0,2,1,1,0]. The algorithm swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After the loop, nums becomes [0,0,1,1,2,2], sorted by color.

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option C

4. Quick Check:

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

Hint: Remember: 0s front, 1s middle, 2s end [OK]

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing order of pointers

4. Identify the bug in the following Dutch Flag algorithm code:

nums = [2, 0, 1]
low, mid, high = 0, 0, len(nums) - 1
while mid < high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

medium

A. The loop condition should be 'mid <= high' instead of 'mid < high'

B. Pointers low and mid are initialized incorrectly

C. Swapping logic for nums[mid] == 0 is wrong

D. The decrement of high should be after incrementing mid

Solution

1. Step 1: Analyze loop condition

   The loop runs while mid < high, so it stops when mid == high, missing last element check.

2. Step 2: Correct loop condition

   It should be mid <= high to process all elements including when mid equals high.

3. Final Answer:

   The loop condition should be 'mid <= high' instead of 'mid < high' -> Option A

4. Quick Check:

   Loop must cover mid == high [OK]

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

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pointer initialization unnecessarily
• Incorrect swap logic for 0 or 2

5. Given an array nums = [1, 2, 0, 1, 2, 0, 1], how many swaps will the Dutch Flag algorithm perform to sort it?

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace swaps during sorting

   Initial: [1,2,0,1,2,0,1] low=0, mid=0, high=6
   - mid=0 (1): mid=1 (no swap)
   - mid=1 (2): swap(1,6) -> [1,1,0,1,2,0,2] high=5 (swap 1)
   - mid=1 (1): mid=2
   - mid=2 (0): swap(0,2) -> [0,1,1,1,2,0,2] low=1 mid=3 (swap 2)
   - mid=3 (1): mid=4
   - mid=4 (2): swap(4,5) -> [0,1,1,1,0,2,2] high=4 (swap 3)
   - mid=4 (0): swap(1,4) -> [0,0,1,1,1,2,2] low=2 mid=5 (swap 4)

2. Step 2: Total swaps counted

   There are 4 swaps in total during the process.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 moves happen [OK]

Common Mistakes:

• Counting pointer moves as swaps
• Missing swaps when swapping with same element
• Not tracing all pointer changes