Sort Colors Two Pointer Dutch Flag in DSA Java

Mental Model

We separate three groups in one pass by moving pointers that track where each color should go.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls to the correct box as you scan through them once.

Index:  0   1   2   3   4   5   6
Array: [2] [0] [2] [1] [1] [0] [0]
Pointers:
 low -> points to next position for 0
 mid -> current element being checked
 high -> points to next position for 2

Dry Run Walkthrough

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

Goal: Sort the array so that all 0s come first, then 1s, then 2s in one pass

Step 1: Check element at mid=0 (value 2), swap with element at high=6, decrease high

[0] [0] [2] [1] [1] [0] [2]
low=0 mid=0 high=5

Why: 2 should be at the end, so swap it with the element at high and reduce high

Step 2: Check element at mid=0 (value 0), swap with element at low=0, increase low and mid

[0] [0] [2] [1] [1] [0] [2]
low=1 mid=1 high=5

Why: 0 should be at the start, so swap with low and move both pointers forward

Step 3: Check element at mid=1 (value 0), swap with element at low=1, increase low and mid

[0] [0] [2] [1] [1] [0] [2]
low=2 mid=2 high=5

Why: 0 should be at the start, swap with low and move pointers

Step 4: Check element at mid=2 (value 2), swap with element at high=5, decrease high

[0] [0] [0] [1] [1] [2] [2]
low=2 mid=2 high=4

Why: 2 should be at the end, swap with high and reduce high

Step 5: Check element at mid=2 (value 0), swap with element at low=2, increase low and mid

[0] [0] [0] [1] [1] [2] [2]
low=3 mid=3 high=4

Why: 0 should be at the start, swap with low and move pointers

Step 6: Check element at mid=3 (value 1), just increase mid

[0] [0] [0] [1] [1] [2] [2]
low=3 mid=4 high=4

Why: 1 is in the middle, just move mid forward

Step 7: Check element at mid=4 (value 1), just increase mid

[0] [0] [0] [1] [1] [2] [2]
low=3 mid=5 high=4

Why: 1 is in the middle, move mid forward ends loop

Result:

[0] -> [0] -> [0] -> [1] -> [1] -> [2] -> [2] -> null

Annotated Code

DSA Java

public class SortColors {
    public static void sortColors(int[] nums) {
        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 { // nums[mid] == 2
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
            }
        }
    }

    public static void printArray(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " -> ");
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0, 0};
        sortColors(nums);
        printArray(nums);
    }
}

while (mid <= high) {

loop until mid pointer passes high pointer to cover all elements

if (nums[mid] == 0) {

if current element is 0, swap with low pointer and move low and mid forward

int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp;

swap elements at low and mid to move 0 to front

low++; mid++;

advance low and mid pointers after placing 0

else if (nums[mid] == 1) { mid++; }

if element is 1, just move mid forward as 1s are in the middle

else { int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp; high--; }

if element is 2, swap with high pointer and decrease high, mid stays to check swapped element

Output

0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array once with pointers moving forward or backward

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to counting sort which uses extra space and two passes, this method sorts in one pass with constant space

Edge Cases

empty array

function completes immediately without changes

DSA Java

while (mid <= high) {

array with all same elements

pointers move quickly without swaps, array remains unchanged

DSA Java

if (nums[mid] == 0) { ... } else if (nums[mid] == 1) { ... } else { ... }

array with only two colors (e.g., 0 and 1)

algorithm still correctly sorts by moving pointers accordingly

DSA Java

while (mid <= high) {

When to Use This Pattern

When you need to sort an array with exactly three distinct values in one pass, use the Dutch National Flag pattern with two pointers to separate groups efficiently.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high when element is 2
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping elements without updating pointers correctly
Fix: Update low and mid after swapping 0, and update high only after swapping 2, keeping mid to recheck

Summary

Sorts an array of 0s, 1s, and 2s in one pass using three pointers.

Use when you want to separate three groups efficiently without extra space.

The key is to move 0s to the front, 2s to the end, and 1s stay in the middle by adjusting pointers carefully.

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