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

Recall & Review

beginner

What is the main idea behind the Dutch National Flag problem?

It is to sort an array containing three different values (like 0, 1, 2) in a single pass using pointers, without extra space.

beginner

In the two-pointer Dutch Flag algorithm, what do the pointers 'low', 'mid', and 'high' represent?

'low' marks the boundary for 0s, 'mid' is the current element under consideration, and 'high' marks the boundary for 2s.

intermediate

Why does the Dutch Flag algorithm swap elements when nums[mid] == 0 or nums[mid] == 2?

Because 0s should be at the start and 2s at the end, swapping moves them to their correct partitions while the mid pointer moves through the array.

beginner

What is the time complexity of the Dutch National Flag sorting algorithm?

O(n), because it makes only one pass through the array.

intermediate

Can the Dutch Flag algorithm be used to sort arrays with more than three distinct values?

No, it is specifically designed for three distinct values. For more values, other sorting methods or multiple passes are needed.

What does the 'mid' pointer do in the Dutch Flag algorithm?

A Points to the last two

B Marks the end of the array

C Tracks the current element being checked

D Points to the first zero

'mid' moves through the array checking each element to decide if it should be swapped.

When nums[mid] == 1, what action does the algorithm take?

A Move high pointer backward

B Swap with nums[high]

C Swap with nums[low]

D Move mid pointer forward

When the element is 1, it is already in the correct middle position, so only mid moves forward.

What is the initial position of the 'high' pointer?

A End of the array

B Start of the array

C Middle of the array

D One past the end

'high' starts at the last index to track where 2s should be placed.

Which of these is NOT true about the Dutch Flag algorithm?

A It sorts in one pass

B It uses extra space proportional to input size

C It uses three pointers

D It swaps elements to correct partitions

The algorithm sorts in-place without extra space.

What happens when nums[mid] == 2 in the algorithm?

A Swap nums[mid] with nums[high] and decrement high

B Swap nums[mid] with nums[low] and increment mid

C Increment mid only

D Decrement low only

2s are swapped to the end by swapping with nums[high], then high moves left.

Explain how the two-pointer Dutch Flag algorithm sorts an array of 0s, 1s, and 2s in one pass.

Think about how each pointer divides the array into sections and how swapping helps.

Describe the advantages and limitations of using the Dutch Flag algorithm for sorting colors.

Consider what makes it fast and when it cannot be used.

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