Sort Colors Two Pointer Dutch Flag in DSA C - 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 complete pass of the two-pointer Dutch Flag algorithm on the input array?

DSA C

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

int main() {
    int nums[] = {2, 0, 2, 1, 1, 0};
    int size = 6;
    sortColors(nums, size);
    // Print array after sorting
    for (int i = 0; i < size; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

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

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

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

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

💡 Hint

Trace the pointers low, mid, and high as the algorithm swaps elements.

The Dutch 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

Number of Swaps in Dutch Flag Algorithm

Given an array of n elements containing only 0s, 1s, and 2s, what is the maximum number of swaps the two-pointer Dutch Flag algorithm will perform in the worst case?

A n^2

B 2n

C n/2

D n

💡 Hint

Consider that each element is swapped at most once or twice.

Each element is moved at most once to its correct position, so the maximum swaps are proportional to n, the array size.

🔧 Debug

advanced

Identify the Bug in Dutch Flag Implementation

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

DSA C

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

A Array not fully sorted because loop condition is incorrect

B Segmentation fault due to invalid memory access

C Infinite loop because mid is never incremented in some cases

D Compilation error due to missing semicolon

💡 Hint

Check the loop condition carefully and how it affects the pointers.

The loop condition should be 'mid <= high' to ensure all elements are processed. Using 'mid < high' skips processing when mid equals high, leaving the array partially unsorted.

❓ Predict Output

advanced

Final Array State After Partial Dutch Flag Execution

What is the array state after executing the Dutch Flag algorithm up to the point where mid pointer reaches index 3 on the input array?

DSA C

int nums[] = {2, 0, 1, 2, 0, 1};
int low = 0, mid = 0, high = 5;
while (mid <= high) {
    if (nums[mid] == 0) {
        int temp = nums[low];
        nums[low] = nums[mid];
        nums[mid] = temp;
        low++;
        mid++;
    } else if (nums[mid] == 1) {
        mid++;
    } else {
        int temp = nums[mid];
        nums[mid] = nums[high];
        nums[high] = temp;
        high--;
    }
    if (mid == 3) break;
}

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

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

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

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

💡 Hint

Simulate each step and watch how low, mid, and high pointers move.

After processing until mid reaches 3, the array partially sorted is [0, 0, 1, 2, 2, 1].

🧠 Conceptual

expert

Why Dutch Flag Algorithm is Optimal for Sorting Colors

Why is the two-pointer Dutch Flag algorithm considered optimal for sorting an array containing only 0s, 1s, and 2s?

A It sorts the array in a single pass with constant extra space

B It uses recursion to divide and conquer the array efficiently

C It sorts the array by counting occurrences and then overwriting

D It uses a built-in sort function optimized for small ranges

💡 Hint

Think about the number of passes and extra memory used.

The Dutch Flag algorithm sorts the array in one pass using only a few pointers and no extra arrays, making it time and space efficient.

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