Sort Colors Two Pointer Dutch Flag in DSA C++

Mental Model

We use two pointers to separate three groups by swapping elements in one pass. This avoids extra space and multiple passes.

Analogy: Imagine sorting red, white, and blue balls into three bins by moving balls between bins with two hands, one hand placing reds and the other placing blues, leaving whites in the middle.

Index: 0  1  2  3  4  5  6
Array: R  W  B  W  R  B  W
Pointers:
 low ↑          mid ↑          high ↑
(R=red=0, W=white=1, B=blue=2)

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: mid points to 2, swap with high (0), then decrease high

0 -> [mid->0] -> 2 -> 1 -> 1 -> 2
low=0, mid=0, high=4

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

Step 2: mid points to 0, swap with low (0), increase low and mid

[low->0] -> 0 -> 2 -> 1 -> 1 -> 2
low=1, mid=1, high=4

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

Step 3: mid points to 2, swap with high (1), decrease high

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

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

Step 4: mid points to 1, just increase mid

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

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

Step 5: mid points to 1, just increase mid

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

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

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0;
    int high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else { // nums[mid] == 2
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

int main() {
    vector<int> nums = {2, 0, 2, 1, 1, 0};
    sortColors(nums);
    for (int num : nums) {
        cout << num << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

while (mid <= high) {

loop until mid passes high to process all elements

if (nums[mid] == 0) {

if current is 0, swap with low pointer to move 0s to front

swap(nums[low], nums[mid]);

swap 0 to front

low++; mid++;

advance low and mid pointers after placing 0

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

if current is 1, just move mid forward

mid++;

skip 1s as they belong in the middle

else { // nums[mid] == 2

if current is 2, swap with high pointer to move 2s to end

swap(nums[mid], nums[high]);

swap 2 to end

high--;

decrease high pointer after placing 2

Output

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

Complexity Analysis

Time: O(n) because we traverse 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 requires two passes and extra space, this method sorts in one pass and constant space

Edge Cases

empty array

function returns immediately without changes

DSA C++

int high = nums.size() - 1;

array with all same elements

no swaps needed, pointers move through array

DSA C++

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

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

swaps and pointer moves handle sorting correctly

DSA C++

if (nums[mid] == 0) { swap(nums[low], nums[mid]); low++; mid++; }

When to Use This Pattern

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

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: Using three separate loops instead of one pass
Fix: Use the two-pointer approach to sort in one pass for better efficiency

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 move 0s to front and 2s to end by swapping, leaving 1s in the middle.

Practice

1. What is the main goal of the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. To find the maximum element in an array

B. To sort any array of integers in ascending order

C. To sort an array containing only 0s, 1s, and 2s in a single pass

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 C

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

easy

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

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

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

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

Solution

1. Step 1: Understand pointer roles

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

2. Step 2: Match initialization

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

3. Final Answer:

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

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 low or mid to n-1 incorrectly
• Initializing all pointers to zero
• Confusing high pointer position

3. What will be the output of the following C++ code snippet?

std::vector<int> nums = {2, 0, 2, 1, 1, 0};
int low = 0, mid = 0, high = nums.size() - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    std::swap(nums[low], nums[mid]);
    low++; mid++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    std::swap(nums[mid], nums[high]);
    high--;
  }
}
for (int num : nums) std::cout << num << " ";

medium

A. 0 0 1 1 2 2

B. 2 2 1 1 0 0

C. 0 1 0 1 2 2

D. 1 0 2 0 1 2

Solution

1. Step 1: Trace the sorting process

   Initially: {2,0,2,1,1,0} - Swap 2 and 0 at low and mid, low=1, mid=1 - mid points to 0, swap with low, low=2, mid=2 - mid points to 2, swap with high (0), high=4 - mid points to 0, swap with low, low=3, mid=3 - mid points to 1, mid++ - mid points to 1, mid++ Loop ends.

2. Step 2: Final array after sorting

   The array becomes: 0 0 1 1 2 2

3. Final Answer:

   0 0 1 1 2 2 -> Option A

4. Quick Check:

   Sorted colors output = 0 0 1 1 2 2 [OK]

Hint: Swap 0s left, 2s right, 1s stay middle [OK]

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing pointer updates

4. Identify the error in the following C++ code implementing the Dutch National Flag algorithm:

int low = 0, mid = 0, high = n - 1;
while (mid < high) {
  if (nums[mid] == 0) {
    std::swap(nums[low], nums[mid]);
    low++;
    mid++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    std::swap(nums[mid], nums[high]);
    high--;
  }
}

medium

A. Pointers low and mid should start at n - 1

B. The high pointer should be incremented instead of decremented

C. Swapping should be done only when nums[mid] == 1

D. The loop condition should be 'mid <= high' instead of 'mid < high'

Solution

1. Step 1: Analyze loop condition

   The loop uses 'mid < high', which misses the case when mid equals high, leaving last element unsorted.

2. Step 2: Correct loop condition

   Changing to 'mid <= high' ensures all elements are processed including when mid equals high.

3. Final Answer:

   The loop condition should be 'mid <= high' instead of 'mid < high' -> Option D

4. Quick Check:

   Loop must cover mid == high for full sorting [OK]

Hint: Use 'mid <= high' to cover all elements [OK]

Common Mistakes:

• Using 'mid < high' misses last element
• Starting pointers incorrectly
• Wrong pointer increments or decrements

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch National Flag algorithm to count how many swaps are performed during sorting?

hard

A. Add a counter variable and increment it each time a swap is done inside the loop

B. Count the number of 0s, 1s, and 2s before sorting

C. Increment a counter every time mid pointer moves

D. Count swaps only when nums[mid] == 1

Solution

1. Step 1: Understand when swaps happen

   Swaps occur when nums[mid] is 0 or 2, swapping with low or high pointers respectively.

2. Step 2: Implement swap counting

   Introduce an integer counter initialized to zero, increment it inside the loop each time std::swap is called.

3. Final Answer:

   Add a counter variable and increment it each time a swap is done inside the loop -> Option A

4. Quick Check:

   Count swaps by incrementing on each swap call [OK]

Hint: Increment counter inside swap blocks only [OK]

Common Mistakes:

• Counting pointer moves instead of swaps
• Counting swaps for 1s which are not swapped
• Counting before sorting instead of during