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

Given the input array [2, 0, 2, 1, 1, 0], what is the state of the array after the first complete pass of the Dutch Flag two-pointer algorithm?

DSA C#

int[] nums = {2, 0, 2, 1, 1, 0};
int low = 0, mid = 0, high = nums.Length - 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--;
    }
    break; // simulate only one pass iteration
}

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

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

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

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

💡 Hint

Focus on what happens when nums[mid] == 2 during the first iteration.

The first iteration swaps nums[mid] (2) with nums[high] (0), resulting in [0, 0, 2, 1, 1, 2].

🧠 Conceptual

intermediate

Understanding Pointer Roles in Dutch Flag Algorithm

In the Dutch Flag two-pointer algorithm for sorting colors, what is the main role of the mid pointer?

A It marks the boundary between 0s and 1s.

B It scans through the array to classify elements.

C It marks the boundary between 1s and 2s.

D It points to the last element in the array.

💡 Hint

Think about which pointer moves through the array checking each element.

The mid pointer moves from start to end, checking each element to decide if it should be swapped or skipped.

🔧 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#

int[] nums = {2, 0, 1};
int low = 0, mid = 0, high = nums.Length - 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 NullReferenceException

B No error, sorts correctly

C IndexOutOfRangeException

D Does not sort correctly

💡 Hint

Check the loop condition and how mid and high pointers move.

The loop condition should be mid <= high. Using mid < high causes the loop to miss processing when mid == high, resulting in incorrect sorting.

❓ Predict Output

advanced

Final Sorted Array After Dutch Flag Algorithm

What is the final sorted array after running the Dutch Flag algorithm on [1, 0, 2, 1, 0]?

DSA C#

int[] nums = {1, 0, 2, 1, 0};
int low = 0, mid = 0, high = nums.Length - 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 [0, 0, 1, 1, 2]

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

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

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

💡 Hint

Remember the algorithm sorts 0s first, then 1s, then 2s.

The algorithm moves all 0s to the front, 1s in the middle, and 2s to the end, resulting in [0, 0, 1, 1, 2].

🧠 Conceptual

expert

Why Dutch Flag Algorithm is Optimal for Sorting Colors

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

A It uses a built-in sort function optimized for three values.

B It uses recursion to divide and conquer the array.

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

D It sorts the array by counting each color first.

💡 Hint

Think about how many times the array is traversed 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 very efficient.

Practice

1. What is the main idea behind the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. Swap elements randomly until sorted

B. Sort the array using built-in sort function

C. Count each color and then overwrite the array

D. Use three pointers to separate 0s, 1s, and 2s in one pass

Solution

1. Step 1: Understand the problem

   The algorithm sorts an array containing only 0s, 1s, and 2s representing colors.

2. Step 2: Use three pointers

   It uses three pointers: low, mid, and high to separate the colors in one pass efficiently.

3. Final Answer:

   Use three pointers to separate 0s, 1s, and 2s in one pass -> Option D

4. Quick Check:

   Three pointers = A [OK]

Hint: Remember three pointers separate colors in one pass [OK]

Common Mistakes:

• Using built-in sort instead of pointers
• Counting colors then rewriting array
• Swapping elements without pointers

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

easy

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

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

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

D. int low = 0, mid = 1, high = nums.Length;

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high starts at last index (length - 1).

2. Step 2: Check initialization correctness

   int low = 0, mid = 0, high = nums.Length - 1; correctly sets low and mid to 0, high to nums.Length - 1.

3. Final Answer:

   int low = 0, mid = 0, high = nums.Length - 1; -> Option A

4. Quick Check:

   Correct pointer init = C [OK]

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

Common Mistakes:

• Setting high to 0 instead of last index
• Starting mid at length - 1
• Using invalid pointer values

3. What will be the output array after running the Dutch Flag algorithm on nums = new int[] {2, 0, 2, 1, 1, 0};?

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, 2, 0, 1, 2]

Solution

1. Step 1: Start with pointers low=0, mid=0, high=5

   Initial array: [2, 0, 2, 1, 1, 0]

2. Step 2: Process elements using Dutch Flag logic

   Swap 2 with 0 at high, move high left; swap 2 with 0 at low; move mid and low accordingly until sorted.

3. Final Answer:

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

4. Quick Check:

   Sorted colors = A [OK]

Hint: Swap 0s left, 2s right, 1s stay middle [OK]

Common Mistakes:

• Not swapping correctly
• Moving pointers incorrectly
• Confusing order of colors

4. Identify the bug in the following C# code snippet for the Dutch Flag algorithm:

int low = 0, mid = 0, high = nums.Length - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    Swap(nums, low, mid);
    low++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    Swap(nums, mid, high);
    high--;
  }
}

medium

A. Swap function parameters are incorrect

B. Missing increment of mid after swapping 0

C. high should be incremented instead of decremented

D. mid should not be incremented when nums[mid] == 1

Solution

1. Step 1: Check pointer increments after swaps

   When nums[mid] == 0, after swapping with low, mid must also increment to avoid infinite loop.

2. Step 2: Identify missing mid++

   The code increments low but misses mid++, causing mid to stay and loop endlessly.

3. Final Answer:

   Missing increment of mid after swapping 0 -> Option B

4. Quick Check:

   Increment mid after 0 swap = D [OK]

Hint: Always increment mid after swapping 0 [OK]

Common Mistakes:

• Forgetting mid++ after swapping 0
• Decrementing high incorrectly
• Incorrect swap parameters

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch Flag algorithm to sort an array that also contains 3s, placing all 3s at the end?

hard

A. Add a fourth pointer and extend the logic to handle 3s at the end

B. Use the same three pointers but treat 3s as 2s

C. Sort the array normally using built-in sort for 3s

D. Ignore 3s since they are already at the end

Solution

1. Step 1: Understand limitation of three pointers

   The original algorithm handles only three values (0,1,2). Adding 3 requires extra handling.

2. Step 2: Introduce a fourth pointer

   Use four pointers to separate 0s, 1s, 2s, and 3s, extending the logic to place 3s at the end.

3. Final Answer:

   Add a fourth pointer and extend the logic to handle 3s at the end -> Option A

4. Quick Check:

   Four pointers for four colors = B [OK]

Hint: Add pointer per unique value for correct sorting [OK]

Common Mistakes:

• Treating 3s as 2s causing wrong order
• Using built-in sort instead of pointers
• Ignoring 3s placement