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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch Flag Algorithm After One Pass

What is the output array after running one full pass of the Dutch National Flag algorithm on the input array?

DSA Java

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--;
    }
}
System.out.println(java.util.Arrays.toString(nums));

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

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

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

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

💡 Hint

Remember the algorithm moves 0s to the front, 2s to the end, and 1s stay in the middle.

The Dutch National Flag algorithm sorts the array in one pass by swapping 0s to the front and 2s to the end, leaving 1s 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 National Flag algorithm, what is the role of the 'mid' pointer during the sorting process?

A It swaps elements with the 'low' pointer only.

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

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

D It points to the last unsorted element from the right.

💡 Hint

Think about which pointer moves forward to check each element.

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

🔧 Debug

advanced

Identify the Bug in Dutch Flag Implementation

What error will occur when running this code snippet for sorting colors using the Dutch National Flag algorithm?

DSA Java

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--;
    }
}
System.out.println(java.util.Arrays.toString(nums));

A The loop misses sorting the last element.

B The array is sorted correctly with no errors.

C The loop condition causes an infinite loop.

D ArrayIndexOutOfBoundsException occurs.

💡 Hint

Check the loop condition carefully and how it affects processing the last element.

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

❓ Predict Output

advanced

Result of Dutch Flag Algorithm on Custom Input

What is the output after sorting the array using the Dutch National Flag algorithm?

DSA Java

int[] nums = {1, 2, 0, 1, 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--;
    }
}
System.out.println(java.util.Arrays.toString(nums));

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

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

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

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

💡 Hint

The algorithm sorts all 0s first, then 1s, then 2s.

After the algorithm completes, the array is sorted with all 0s at the front, followed by 1s, then 2s at the end.

🧠 Conceptual

expert

Why Dutch National Flag Algorithm is O(n)

Why does the Dutch National Flag algorithm run in linear time O(n) despite having nested swaps inside the loop?

A Because the swaps are done in constant time and the loop runs n times.

B Because each element is visited at most twice, and pointers only move forward or backward without revisiting elements.

C Because the algorithm uses recursion to reduce time complexity.

D Because it sorts the array by dividing it into three separate arrays first.

💡 Hint

Think about how many times each element is processed and how pointers move.

Each element is processed once or twice at most, and the pointers move in one direction without revisiting elements, making the algorithm linear time.

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 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 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 way to initialize the pointers for the Dutch Flag algorithm in Java?

easy

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

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

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

D. int low = 0, mid = 0, high = arr.length - 1;

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Match initialization with roles

   int low = 0, mid = 0, high = arr.length - 1; correctly sets low and mid to 0, and high to last index (arr.length - 1).

3. Final Answer:

   int low = 0, mid = 0, high = arr.length - 1; -> Option D

4. Quick Check:

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

Hint: Low and mid start at 0, high at array end [OK]

Common Mistakes:

• Setting pointers all to zero
• Starting high pointer at 0 instead of end
• Confusing mid and high initial positions

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

medium

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

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

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

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

Solution

1. Step 1: Apply Dutch Flag sorting logic

   Start with low=0, mid=0, high=5. Swap 2 with 0 at low, move pointers accordingly to group 0s, then 1s, then 2s.

2. Step 2: Final sorted array

   After sorting, the array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: 0s first, then 1s, then 2s after sorting [OK]

Common Mistakes:

• Not swapping correctly
• Mixing order of 1s and 2s
• Assuming original order stays same

4. Identify the error in this Java code snippet for the Dutch Flag algorithm:

int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
  if (arr[mid] == 0) {
    swap(arr, low, mid);
    low++;
  } else if (arr[mid] == 1) {
    mid++;
  } else {
    swap(arr, mid, high);
    high--;
  }
}

medium

A. Swap function parameters are wrong

B. Incorrect condition in while loop

C. Missing increment of mid pointer after swapping 0

D. No error, code is correct

Solution

1. Step 1: Analyze pointer increments after swaps

   When swapping 0, mid pointer must also increment to avoid infinite loop.

2. Step 2: Identify missing mid++ after swapping 0

   Code increments low but forgets to increment mid after swapping 0, causing repeated processing of same element.

3. Final Answer:

   Missing increment of mid pointer after swapping 0 -> Option C

4. Quick Check:

   mid++ needed after swapping 0 [OK]

Hint: Always increment mid after swapping 0 [OK]

Common Mistakes:

• Forgetting to increment mid after swap
• Changing while loop condition incorrectly
• Swapping wrong indices

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

hard

A. 6

B. 4

C. 5

D. 7

Solution

1. Step 1: Trace swaps during sorting

   Initial array: [1,2,0,2,1,0,0,2,1]. Swaps occur when 0 or 2 are moved. Counting swaps:
   - Swap 1: mid=1 (2) with high=8
   - Swap 2: mid=2 (0) with low=0
   - Swap 3: mid=3 (2) with high=7
   - Swap 4: mid=3 (2) with high=6
   - Swap 5: mid=3 (0) with low=1
   - Swap 6: mid=5 (0) with low=2

2. Step 2: Total swaps counted

   Total swaps performed are 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 move positions [OK]

Common Mistakes:

• Counting swaps only for 0s
• Ignoring swaps when swapping with same value
• Miscounting pointer moves as swaps