Sort Colors Two Pointer Dutch Flag in DSA C

Mental Model

We separate three colors by moving pointers that divide the array into parts for each color.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls one by one to the correct box using two hands.

Index: 0  1  2  3  4  5  6
Array: R  W  B  W  R  B  W
Pointers:
 low ↑ mid ↑ high ↑

Dry Run Walkthrough

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

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

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

[2, 0, 2, 1, 1, 0]
 low=0 mid=0 high=5
After swap:
[0, 0, 2, 1, 1, 2]
 low=0 mid=0 high=4

Why: We move 2 to the end because 2s belong at the right side

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

[0, 0, 2, 1, 1, 2]
 low=0 mid=0 high=4
After swap:
[0, 0, 2, 1, 1, 2]
 low=1 mid=1 high=4

Why: 0s belong at the left side, so we move low and mid forward

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

[0, 0, 2, 1, 1, 2]
 low=1 mid=1 high=4
After swap:
[0, 0, 2, 1, 1, 2]
 low=2 mid=2 high=4

Why: Continue moving 0s to the left

Step 4: Check mid=2 (value 2), swap with high=4 (value 1), decrease high

[0, 0, 2, 1, 1, 2]
 low=2 mid=2 high=4
After swap:
[0, 0, 1, 1, 2, 2]
 low=2 mid=2 high=3

Why: Move 2 to the right side

Step 5: Check mid=2 (value 1), increase mid

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

Why: 1s belong in the middle, so just move mid forward

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

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

Why: Continue moving mid forward for 1s

Step 7: mid=4 is greater than high=3, stop

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

Why: Sorting is complete when mid passes high

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 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--;
        }
    }
}

void printArray(int* nums, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", nums[i]);
        if (i != size - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int nums[] = {2, 0, 2, 1, 1, 0};
    int size = sizeof(nums) / sizeof(nums[0]);
    sortColors(nums, size);
    printArray(nums, size);
    return 0;
}

while (mid <= high) {

continue sorting until mid passes high

if (nums[mid] == 0) {

found 0, swap with low to move 0 to left

low++; mid++;

advance low and mid pointers after placing 0

else if (nums[mid] == 1) {

1 is in correct middle place, just move mid

mid++;

advance mid pointer for 1

else { // nums[mid] == 2

found 2, swap with high to move 2 to right

high--;

decrease high pointer after placing 2

Output

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

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer

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

vs Alternative: Compared to counting sort which uses extra space, this uses constant space and one pass

Edge Cases

empty array

function does nothing and exits safely

DSA C

while (mid <= high) {

array with all same colors

array remains unchanged after sorting

DSA C

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

array with only two colors

algorithm correctly sorts the two colors by swapping

DSA C

while (mid <= high) {

When to Use This Pattern

When you see a problem asking to sort three distinct values quickly and in place, use the Dutch National Flag two-pointer pattern to separate them efficiently.

Common Mistakes

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

Mistake: Swapping incorrectly between pointers causing infinite loops
Fix: Always swap nums[mid] with nums[low] or nums[high] carefully and update pointers accordingly

Summary

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

Use when you need to sort three distinct values efficiently without extra space.

The key is to maintain three regions with pointers low, mid, and high to separate colors.

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 sorting goal

   The goal is to sort these values so that all 0s come first, then all 1s, and finally all 2s, in one pass without extra space.

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

easy

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

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

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

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

Solution

1. Step 1: Recall pointer roles

   Low starts at 0 to track the boundary of 0s, mid starts at 0 to scan elements, high starts at n-1 to track boundary of 2s.

2. Step 2: Match initialization

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

3. Final Answer:

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

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 high to 0 instead of n-1
• Starting mid at n-1
• Confusing low and high initialization

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

medium

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

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

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

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

Solution

1. Step 1: Trace the algorithm on input

   Initial array: {2, 0, 2, 1, 1, 0}. After sorting: all 0s first, then 1s, then 2s.

2. Step 2: Final sorted array

   Sorted array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort 0s, then 1s, then 2s in one pass [OK]

Common Mistakes:

• Not sorting 0s and 2s correctly
• Mixing order of 1s and 0s
• Outputting original array

4. Identify the error in this C code snippet implementing the Dutch National Flag algorithm:

void sortColors(int* arr, int n) {
  int low = 0, mid = 0, high = n - 1;
  while (mid <= high) {
    if (arr[mid] == 0) {
      int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
      low++;
      mid++;
    } else if (arr[mid] == 1) {
      mid++;
    } else {
      int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
      high--;
    }
  }
}

medium

A. Missing decrement of high after swapping with low

B. Missing increment of mid after swapping with low

C. Missing increment of mid after swapping with high

D. Incorrect initialization of pointers

Solution

1. Step 1: Analyze pointer increments

   When swapping arr[mid] with arr[low] (for 0), low is incremented but mid is not incremented, causing infinite loop or wrong behavior.

2. Step 2: Correct pointer movement

   After swapping with low, both low and mid should be incremented to move forward.

3. Final Answer:

   Missing increment of mid after swapping with low -> Option B

4. Quick Check:

   Increment mid after swapping with low [OK]

Hint: Increment mid after swapping with low pointer [OK]

Common Mistakes:

• Not incrementing mid after swapping with low
• Incrementing mid after swapping with high
• Incorrect pointer initialization

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

hard

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Trace swaps during sorting

   Initial array: {1, 2, 0, 1, 2, 0, 1}
   - Swap 1: mid=1 (2) with high=6 (1) -> [1,1,0,1,2,0,2], high=5
   mid=1 now 1 -> mid=2
   - Swap 2: mid=2 (0) with low=0 (1) -> [0,1,1,1,2,0,2], low=1, mid=3
   mid=3 (1) -> mid=4
   - Swap 3: mid=4 (2) with high=5 (0) -> [0,1,1,1,0,2,2], high=4
   mid=4 now 0 ->
   - Swap 4: mid=4 (0) with low=1 (1) -> [0,0,1,1,1,2,2], low=2, mid=5 (stop)

2. Step 2: Count total swaps

   Total swaps counted are 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps only when actual element exchange happens [OK]

Common Mistakes:

• Counting pointer increments as swaps
• Missing swaps when swapping with high
• Undercounting swaps for consecutive swaps on same mid