Sort Colors Two Pointer Dutch Flag in DSA C++ - Deep Dive

Overview - Sort Colors Two Pointer Dutch Flag

What is it?

Sort Colors Two Pointer Dutch Flag is a method to sort an array containing only three different values, usually represented as 0, 1, and 2. The goal is to rearrange the array so that all 0s come first, then all 1s, and finally all 2s, without using extra space. This is done efficiently in one pass using two pointers and a current index.

Why it matters

This method solves the problem of sorting limited distinct elements quickly and in-place, which is common in real-world tasks like sorting objects by categories or priorities. Without this approach, sorting such arrays might require extra memory or multiple passes, making programs slower and less efficient.

Where it fits

Before learning this, you should understand arrays and basic sorting concepts. After mastering this, you can explore more complex sorting algorithms and two-pointer techniques for other problems.

Mental Model

Core Idea

Use two pointers to separate three groups by swapping elements in one pass without extra space.

Think of it like...

Imagine sorting red, white, and blue balls in a line by moving red balls to the left, blue balls to the right, and white balls stay in the middle, all by swapping balls as you scan once.

Start: [0,1,2,0,1,2]
Pointers:
  low -> start of array (for 0s)
  mid -> current element
  high -> end of array (for 2s)

Process:
[low]---[mid]---[high]
  |       |       |
  0       1       2

Swap 0 to low side, 2 to high side, 1 stays in middle.

Result:
0 -> 1 -> 2 -> sorted array

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem of sorting an array with only three distinct values: 0, 1, and 2.

You have an array like [2, 0, 2, 1, 1, 0]. Your task is to sort it so all 0s come first, then 1s, then 2s. This is simpler than general sorting because only three values exist.

Result

Recognize the problem is about grouping three types of elements, not general sorting.

Understanding the problem constraints allows us to design a specialized, efficient solution instead of using general sorting.

2

Foundation

Basic Array Traversal and Swapping

Concept: Learn how to swap elements in an array and traverse it using indexes.

Swapping means exchanging two elements' positions. For example, swapping elements at positions 0 and 1 in [2, 0, 1] results in [0, 2, 1]. Traversing means moving through the array from start to end using an index.

Result

Ability to swap elements and move through the array step-by-step.

Mastering swapping and traversal is essential because the sorting method relies on swapping elements while scanning the array once.

3

Intermediate

Introducing Two Pointers and One Pass

🤔Before reading on: do you think we need to scan the array multiple times or just once to sort all colors? Commit to your answer.

Concept: Use two pointers to track boundaries for 0s and 2s while scanning the array once with a third pointer.

We keep three pointers: low (start for 0s), mid (current element), and high (end for 2s). We move mid from start to high. If mid points to 0, swap with low and move both forward. If mid points to 2, swap with high and move high backward. If mid points to 1, just move mid forward.

Result

Array sorted in one pass with all 0s at start, 1s in middle, and 2s at end.

Using two pointers to separate groups while scanning once saves time and space compared to multiple scans or extra arrays.

4

Intermediate

Handling Edge Cases and Equal Elements

🤔Before reading on: do you think the algorithm works correctly if the array has only one type of element? Commit to your answer.

Concept: The method handles arrays with all elements the same or missing some colors without extra changes.

If the array has only 0s, the low and mid pointers move through without swaps. If only 2s, swaps happen with high pointer. The algorithm naturally handles these cases by its pointer movements and conditions.

Result

Algorithm correctly sorts arrays with any combination of 0, 1, and 2, including all same elements.

Knowing the algorithm gracefully handles edge cases increases confidence in its robustness.

5

Intermediate

Dry Run Example with Step-by-Step Swaps

🤔Before reading on: predict the array state after the first swap when starting with [2,0,1]. Commit to your answer.

Concept: Walk through the algorithm step-by-step on a sample array to see how pointers move and swaps happen.

Start: [2,0,1], low=0, mid=0, high=2 mid=0 points to 2 (swap with high): swap positions 0 and 2 -> [1,0,2], high=1 mid=0 points to 1 (just move mid): mid=1 mid=1 points to 0 (swap with low): swap positions 1 and 0 -> [0,1,2], low=1, mid=2 mid > high, stop. Sorted: [0,1,2]

Result

Sorted array [0,1,2] after swaps and pointer moves.

Step-by-step dry runs reveal how pointer logic and swaps achieve sorting efficiently.

6

Advanced

Implementing the Algorithm in C++

🤔Before reading on: do you think the algorithm requires extra memory or works in-place? Commit to your answer.

Concept: Write complete C++ code implementing the two-pointer Dutch National Flag algorithm.

void sortColors(vector& nums) { int low = 0, mid = 0, 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--; } } } // Example usage: // vector arr = {2,0,2,1,1,0}; // sortColors(arr); // Output: 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Result

Sorted array printed as 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null after calling sortColors.

Implementing the algorithm solidifies understanding and shows how in-place sorting is achieved with minimal code.

7

Expert

Algorithm Efficiency and Limitations

🤔Before reading on: do you think this algorithm is optimal for sorting any array or only arrays with three distinct values? Commit to your answer.

Concept: Analyze time and space complexity and understand when this algorithm is best used.

The algorithm runs in O(n) time because it scans the array once. It uses O(1) extra space since swaps happen in-place. However, it only works correctly when the array has exactly three distinct values. For more values, other sorting methods are needed.

Result

Recognize the algorithm is optimal for three-value sorting but limited beyond that.

Knowing the algorithm's efficiency and limits helps choose the right tool for different sorting problems.

Under the Hood

The algorithm maintains three regions in the array: all elements before 'low' are 0s, elements between 'low' and 'mid' are 1s, and elements after 'high' are 2s. The 'mid' pointer scans elements and swaps them to their correct region by exchanging with 'low' or 'high'. This rearrangement happens in-place without extra memory.

Why designed this way?

It was designed by Edsger Dijkstra to solve the Dutch National Flag problem efficiently. The design avoids multiple passes or extra space by cleverly using pointers to track boundaries of each color group, making it optimal for this specific sorting task.

Array indices: 0 1 2 3 4 5
Values:       0 1 2 0 1 2

Pointers:
[low]----[mid]--------[high]
  |        |             |
  0        2             5

Regions:
[0..low-1]: all 0s
[low..mid-1]: all 1s
[mid..high]: unknown
[high+1..end]: all 2s

Myth Busters - 3 Common Misconceptions

Quick: Do you think this algorithm can sort arrays with more than three distinct values correctly? Commit to yes or no.

Common Belief: This algorithm can sort any array regardless of how many distinct values it has.

Reality: The algorithm only works correctly when the array has exactly three distinct values (like 0,1,2). For more values, it will not sort properly.

Why it matters: Using this algorithm on arrays with more values leads to incorrect sorting results, causing bugs and wrong outputs.

Quick: Do you think the algorithm requires extra memory proportional to the array size? Commit to yes or no.

Common Belief: Sorting requires extra memory to hold temporary arrays or copies.

Reality: This algorithm sorts the array in-place using only a few pointers, so it uses constant extra memory (O(1)).

Why it matters: Understanding in-place sorting helps write memory-efficient programs, especially important for large data.

Quick: Do you think the algorithm always moves the mid pointer forward after a swap? Commit to yes or no.

Common Belief: After every swap, the current pointer moves forward.

Reality: When swapping with the high pointer (for 2s), the mid pointer does NOT move forward immediately because the swapped element needs to be checked.

Why it matters: Incorrect pointer movement causes skipping elements and incorrect sorting.

Expert Zone

1

Swapping with the high pointer requires careful handling because the swapped element might be 0, 1, or 2, so mid must not advance immediately.

2

The algorithm's in-place nature avoids extra memory but requires careful pointer updates to prevent infinite loops or missed elements.

3

This method can be generalized to problems where elements belong to a small fixed set of categories, but requires adaptation for more than three categories.

When NOT to use

Avoid using this algorithm when the array has more than three distinct values or when stability (preserving original order of equal elements) is required. Instead, use counting sort or comparison-based stable sorts like mergesort.

Production Patterns

In production, this algorithm is used for quick categorization tasks like sorting flags, colors, or priority levels in UI rendering, network packet classification, or any scenario with three fixed categories needing fast in-place sorting.

Connections

Counting Sort

Alternative approach for sorting limited distinct values

Counting sort also sorts arrays with few distinct values efficiently but uses extra memory, while Dutch Flag algorithm sorts in-place.

Two Pointer Technique

Builds on the general two pointer pattern for array problems

Understanding this algorithm deepens grasp of two pointer methods used in many array and string problems.

Traffic Light Control Systems

Real-world system with three states similar to three colors

Just like sorting colors into groups, traffic lights manage three states (red, yellow, green) in order, showing how categorization applies beyond programming.

Common Pitfalls

#1 Moving the mid pointer forward after swapping with high pointer.

Wrong approach:

if (nums[mid] == 2) {
swap(nums[mid], nums[high]);
high--;
mid++; // wrong: mid should not move here
}

Correct approach:

if (nums[mid] == 2) {
swap(nums[mid], nums[high]);
high--;
// mid stays to check swapped element
}

Root cause:

Misunderstanding that the swapped element from the end might be 0, 1, or 2 and needs checking before moving mid.

#2 Using extra arrays to store colors instead of sorting in-place.

Wrong approach:

vector zeros, ones, twos;
for (int num : nums) {
if (num == 0) zeros.push_back(num);
else if (num == 1) ones.push_back(num);
else twos.push_back(num);
}
// then combine zeros + ones + twos

Correct approach:

Use two pointers and mid pointer to swap elements in-place without extra arrays.

Root cause:

Not realizing the problem can be solved efficiently without extra memory.

#3 Assuming the algorithm works for any number of distinct values.

Wrong approach:

Applying the same two-pointer swaps on an array with values 0,1,2,3 without modification.

Correct approach:

Use other sorting algorithms like counting sort or quicksort for more than three distinct values.

Root cause:

Overgeneralizing the Dutch Flag algorithm beyond its intended scope.

Key Takeaways

The Dutch National Flag algorithm sorts arrays with exactly three distinct values efficiently in one pass using two pointers and a current index.

It works in-place with constant extra memory by swapping elements to their correct regions while scanning the array once.

Careful pointer movement is crucial: mid pointer moves differently depending on the value swapped to avoid skipping elements.

This algorithm is optimal for three-value sorting but not suitable for arrays with more distinct values or when stability is required.

Understanding this method deepens knowledge of two-pointer techniques and specialized sorting algorithms for constrained problems.

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