Sort Colors Two Pointer Dutch Flag in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch Flag Algorithm After Sorting

What is the output of the array after running the Dutch Flag sorting algorithm on the input array?

DSA C++

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

int main() {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

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

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

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

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

💡 Hint

Remember the Dutch Flag algorithm sorts 0s, then 1s, then 2s in one pass.

The algorithm uses three pointers to sort the array in one pass. It moves all 0s to the front, 2s to the end, and 1s remain in the middle. The final sorted array is [0, 0, 1, 1, 2, 2].

🧠 Conceptual

intermediate

Understanding Pointer Roles in Dutch Flag Algorithm

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

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

B It swaps elements with the 'low' pointer.

C It points to the last 2 in the array.

D It scans through the array to classify elements as 0, 1, or 2.

💡 Hint

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

The 'mid' pointer moves through the array from start to end, checking each element to decide if it should be swapped to the front (0) or back (2), or left in place (1).

🔧 Debug

advanced

Identify the Bug in Dutch Flag Implementation

What error will occur when running this code snippet for the Dutch Flag algorithm?

DSA C++

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid < high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

A The loop condition causes some elements to be skipped, resulting in incorrect sorting.

B The code will cause a runtime error due to out-of-bounds access.

C The code will enter an infinite loop.

D The code will compile but produce a reversed sorted array.

💡 Hint

Check the loop condition carefully and how it affects processing all elements.

The loop condition 'mid < high' stops the loop before 'mid' reaches 'high', so the last elements are not processed, causing incorrect sorting.

❓ Predict Output

advanced

Final Array State After Partial Dutch Flag Steps

Given the initial array and partial steps of the Dutch Flag algorithm, what is the array state after the first swap?

DSA C++

vector<int> nums = {2, 0, 1, 2, 0, 1};
int low = 0, mid = 0, high = nums.size() - 1;
if (nums[mid] == 2) {
    swap(nums[mid], nums[high]);
    high--;
}
// What is the array now?

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

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

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

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

💡 Hint

Swap the first and last elements because nums[mid] is 2.

Swapping nums[0] (2) with nums[5] (1) results in [1, 0, 1, 2, 0, 2].

🧠 Conceptual

expert

Why Does Dutch Flag Algorithm Use Three Pointers?

Why does the Dutch Flag algorithm use three pointers (low, mid, high) instead of just one or two?

A To sort the array in descending order.

B To separate the array into three parts: all 0s, all 1s, and all 2s efficiently in one pass.

C To reduce the space complexity from O(n) to O(1).

D To allow parallel processing of the array elements.

💡 Hint

Think about how the algorithm divides the array during sorting.

The three pointers help partition the array into three sections: 0s at the front, 1s in the middle, and 2s at the end, all in one pass without extra space.

Practice

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

easy

A. To find the maximum element in an array

B. To sort any array of integers in ascending order

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

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 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 C

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 of pointers in the Dutch National Flag algorithm in C++?

easy

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

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

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

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

Solution

1. Step 1: Understand pointer roles

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

2. Step 2: Match initialization

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

3. Final Answer:

   int low = 0, mid = 0, high = n - 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:

• Setting low or mid to n-1 incorrectly
• Initializing all pointers to zero
• Confusing high pointer position

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

std::vector<int> nums = {2, 0, 2, 1, 1, 0};
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    std::swap(nums[low], nums[mid]);
    low++; mid++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    std::swap(nums[mid], nums[high]);
    high--;
  }
}
for (int num : nums) std::cout << num << " ";

medium

A. 0 0 1 1 2 2

B. 2 2 1 1 0 0

C. 0 1 0 1 2 2

D. 1 0 2 0 1 2

Solution

1. Step 1: Trace the sorting process

   Initially: {2,0,2,1,1,0} - Swap 2 and 0 at low and mid, low=1, mid=1 - mid points to 0, swap with low, low=2, mid=2 - mid points to 2, swap with high (0), high=4 - mid points to 0, swap with low, low=3, mid=3 - mid points to 1, mid++ - mid points to 1, mid++ Loop ends.

2. Step 2: Final array after sorting

   The array becomes: 0 0 1 1 2 2

3. Final Answer:

   0 0 1 1 2 2 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing pointer updates

4. Identify the error in the following C++ code implementing the Dutch National Flag algorithm:

int low = 0, mid = 0, high = n - 1;
while (mid < high) {
  if (nums[mid] == 0) {
    std::swap(nums[low], nums[mid]);
    low++;
    mid++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    std::swap(nums[mid], nums[high]);
    high--;
  }
}

medium

A. Pointers low and mid should start at n - 1

B. The high pointer should be incremented instead of decremented

C. Swapping should be done only when nums[mid] == 1

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

Solution

1. Step 1: Analyze loop condition

   The loop uses 'mid < high', which misses the case when mid equals high, leaving last element unsorted.

2. Step 2: Correct loop condition

   Changing to 'mid <= high' ensures all elements are processed including when mid equals high.

3. Final Answer:

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

4. Quick Check:

   Loop must cover mid == high for full sorting [OK]

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

Common Mistakes:

• Using 'mid < high' misses last element
• Starting pointers incorrectly
• Wrong pointer increments or decrements

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch National Flag algorithm to count how many swaps are performed during sorting?

hard

A. Add a counter variable and increment it each time a swap is done inside the loop

B. Count the number of 0s, 1s, and 2s before sorting

C. Increment a counter every time mid pointer moves

D. Count swaps only when nums[mid] == 1

Solution

1. Step 1: Understand when swaps happen

   Swaps occur when nums[mid] is 0 or 2, swapping with low or high pointers respectively.

2. Step 2: Implement swap counting

   Introduce an integer counter initialized to zero, increment it inside the loop each time std::swap is called.

3. Final Answer:

   Add a counter variable and increment it each time a swap is done inside the loop -> Option A

4. Quick Check:

   Count swaps by incrementing on each swap call [OK]

Hint: Increment counter inside swap blocks only [OK]

Common Mistakes:

• Counting pointer moves instead of swaps
• Counting swaps for 1s which are not swapped
• Counting before sorting instead of during