Sort Colors Two Pointer Dutch Flag in DSA Java - Build from Scratch

Sort Colors Using Two Pointer Dutch Flag Algorithm

📖 Scenario: Imagine you have a box of colored balls represented by numbers: 0 for red, 1 for white, and 2 for blue. You want to arrange them so that all reds come first, then whites, and then blues, just like sorting the colors of the Dutch flag.

🎯 Goal: You will write a Java program that sorts an array of integers containing only 0s, 1s, and 2s using the two-pointer Dutch Flag algorithm.

📋 What You'll Learn

Create an integer array called colors with the exact values {2, 0, 2, 1, 1, 0}.

Create two integer variables called low and high to represent the start and end pointers.

Use a while loop with a pointer current to sort the array in-place using the Dutch Flag algorithm.

Print the sorted colors array as a sequence of numbers separated by spaces.

💡 Why This Matters

🌍 Real World

Sorting colors or categories quickly is useful in image processing, organizing items, or grouping data efficiently.

💼 Career

Understanding two-pointer techniques and in-place sorting is important for coding interviews and optimizing algorithms in software development.

1

Create the colors array

Create an integer array called colors with the exact values {2, 0, 2, 1, 1, 0}.

DSA Java

// Create the colors array with values {2, 0, 2, 1, 1, 0}
// Your code here

Hint

Use int[] colors = {2, 0, 2, 1, 1, 0}; to create the array.

2

Initialize pointers for sorting

Add two integer variables called low and high. Set low to 0 and high to the last index of the colors array.

DSA Java

public class SortColors {
    public static void main(String[] args) {
        int[] colors = {2, 0, 2, 1, 1, 0};
        // Initialize low and high pointers
        // Your code here
    }
}

Hint

Set low to 0 and high to colors.length - 1.

3

Sort the colors array using two pointers

Add an integer variable current set to 0. Use a while loop with the condition current <= high. Inside the loop, use if statements to swap elements and move pointers according to the Dutch Flag algorithm.

DSA Java

public class SortColors {
    public static void main(String[] args) {
        int[] colors = {2, 0, 2, 1, 1, 0};
        int low = 0;
        int high = colors.length - 1;
        // Sort colors using Dutch Flag algorithm
        // Your code here
    }
}

Hint

Use three pointers: low, current, and high. Swap elements when colors[current] is 0 or 2, and move pointers accordingly.

4

Print the sorted colors array

Use a for loop to print each element of the colors array separated by spaces on a single line.

DSA Java

public class SortColors {
    public static void main(String[] args) {
        int[] colors = {2, 0, 2, 1, 1, 0};
        int low = 0;
        int high = colors.length - 1;
        int current = 0;

        while (current <= high) {
            if (colors[current] == 0) {
                int temp = colors[low];
                colors[low] = colors[current];
                colors[current] = temp;
                low++;
                current++;
            } else if (colors[current] == 2) {
                int temp = colors[high];
                colors[high] = colors[current];
                colors[current] = temp;
                high--;
            } else {
                current++;
            }
        }
        // Print the sorted colors array
        // Your code here
    }
}

Hint

Use a for loop to print each element followed by a space.

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