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

Recall & Review

beginner

What is the main idea behind the Dutch National Flag algorithm for sorting colors?

It uses three pointers to separate the array into three parts: all 0s to the left, all 2s to the right, and all 1s in the middle, sorting the colors in one pass.

beginner

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

The pointers represent: low - boundary for 0s, mid - current element under consideration, high - boundary for 2s.

intermediate

Why does the Dutch Flag algorithm run in O(n) time?

Because it makes only one pass through the array, moving elements to their correct positions using swaps without extra space.

beginner

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 increment both low and mid pointers.

beginner

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

Swap the element at mid with the element at high, then decrement the high pointer without incrementing mid immediately.

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

A At the last index of the array

B At the first index of the array

C At the middle of the array

D At the second index of the array

The 'high' pointer starts at the last index to track the boundary for 2s.

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

A Swap with low pointer and increment both

B Swap with high pointer and decrement high

C Just increment mid pointer

D Stop the algorithm

When mid points to 1, it is already in the correct middle section, so just move mid forward.

What is the space complexity of the Dutch Flag algorithm?

A O(log n)

B O(1)

C O(n)

D O(n^2)

The algorithm sorts the array in place using constant extra space.

Which of these is NOT a color represented in the Sort Colors problem?

A 0

B 1

C 2

D 3

The problem only involves three colors represented by 0, 1, and 2.

What condition ends the main loop in the Dutch Flag algorithm?

A When mid > high

B When low > high

C When mid == low

D When mid < low

The loop runs while mid pointer is less than or equal to high pointer.

Explain the step-by-step process of the Dutch Flag algorithm for sorting colors.

Think about how the array is divided into three parts and how each color is placed.

Why is the Dutch Flag algorithm more efficient than sorting the array using a general sorting method?

Consider the problem constraints and how the algorithm uses them.

Practice

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

easy

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

B. To sort any array of integers in ascending order

C. To find the maximum element in an array

D. To reverse the elements of an array

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 sorting goal

   The goal is to sort these values so that all 0s come first, then all 1s, and finally all 2s, in one pass without extra space.

3. Final Answer:

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

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 integer array
• Confusing it with general sorting algorithms
• Assuming it reverses the array

2. Which of the following is the correct initialization for the pointers in the Dutch National Flag algorithm in C?

easy

A. int low = 0, mid = 0, high = n - 1;

B. int low = n - 1, mid = 0, high = 0;

C. int low = 0, mid = n - 1, high = 0;

D. int low = 0, mid = 0, high = 0;

Solution

1. Step 1: Recall pointer roles

   Low starts at 0 to track the boundary of 0s, mid starts at 0 to scan elements, high starts at n-1 to track boundary of 2s.

2. Step 2: Match initialization

   Only int low = 0, mid = 0, high = n - 1; correctly initializes low and mid at 0 and high at n-1.

3. Final Answer:

   int low = 0, mid = 0, high = n - 1; -> Option A

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:

• Setting high to 0 instead of n-1
• Starting mid at n-1
• Confusing low and high initialization

3. What will be the output array after running the Dutch National Flag algorithm on arr = {2, 0, 2, 1, 1, 0}?

medium

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

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

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

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

Solution

1. Step 1: Trace the algorithm on input

   Initial array: {2, 0, 2, 1, 1, 0}. After sorting: all 0s first, then 1s, then 2s.

2. Step 2: Final sorted array

   Sorted array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort 0s, then 1s, then 2s in one pass [OK]

Common Mistakes:

• Not sorting 0s and 2s correctly
• Mixing order of 1s and 0s
• Outputting original array

4. Identify the error in this C code snippet implementing the Dutch National Flag algorithm:

void sortColors(int* arr, int n) {
  int low = 0, mid = 0, high = n - 1;
  while (mid <= high) {
    if (arr[mid] == 0) {
      int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
      low++;
      mid++;
    } else if (arr[mid] == 1) {
      mid++;
    } else {
      int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
      high--;
    }
  }
}

medium

A. Missing decrement of high after swapping with low

B. Missing increment of mid after swapping with low

C. Missing increment of mid after swapping with high

D. Incorrect initialization of pointers

Solution

1. Step 1: Analyze pointer increments

   When swapping arr[mid] with arr[low] (for 0), low is incremented but mid is not incremented, causing infinite loop or wrong behavior.

2. Step 2: Correct pointer movement

   After swapping with low, both low and mid should be incremented to move forward.

3. Final Answer:

   Missing increment of mid after swapping with low -> Option B

4. Quick Check:

   Increment mid after swapping with low [OK]

Hint: Increment mid after swapping with low pointer [OK]

Common Mistakes:

• Not incrementing mid after swapping with low
• Incrementing mid after swapping with high
• Incorrect pointer initialization

5. Given an array arr = {1, 2, 0, 1, 2, 0, 1}, how many swaps will the Dutch National Flag algorithm perform to sort it?

hard

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Trace swaps during sorting

   Initial array: {1, 2, 0, 1, 2, 0, 1}
   - Swap 1: mid=1 (2) with high=6 (1) -> [1,1,0,1,2,0,2], high=5
   mid=1 now 1 -> mid=2
   - Swap 2: mid=2 (0) with low=0 (1) -> [0,1,1,1,2,0,2], low=1, mid=3
   mid=3 (1) -> mid=4
   - Swap 3: mid=4 (2) with high=5 (0) -> [0,1,1,1,0,2,2], high=4
   mid=4 now 0 ->
   - Swap 4: mid=4 (0) with low=1 (1) -> [0,0,1,1,1,2,2], low=2, mid=5 (stop)

2. Step 2: Count total swaps

   Total swaps counted are 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps only when actual element exchange happens [OK]

Common Mistakes:

• Counting pointer increments as swaps
• Missing swaps when swapping with high
• Undercounting swaps for consecutive swaps on same mid