Sort Colors Two Pointer Dutch Flag in DSA C++ - Execution Trace

Concept Flow - Sort Colors Two Pointer Dutch Flag

Initialize pointers: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Inspect nums[mid

↓

Swap nums[low

↓

If 1: mid++

↓

If 2: Swap nums[mid

↓

Repeat check mid <= high?

We use three pointers low, mid, and high to sort colors by swapping 0s to front, 2s to end, and 1s stay in middle.

Execution Sample

DSA C++

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

Sorts an array of 0s,1s,2s by moving 0s left, 2s right, and 1s stay in place.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes	Visual State
1	Initialize pointers	0	0	7	[2,0,2,1,1,0,0,2]	low=0, mid=0, high=7	2 -> 0 -> 2 -> 1 -> 1 -> 0 -> 0 -> 2
2	Check nums[mid]=2, swap nums[mid] and nums[high], high--	0	0	6	[2,0,2,1,1,0,0,2]	Swap nums[0]<->nums[7], high=6	2 -> 0 -> 2 -> 1 -> 1 -> 0 -> 0 -> 2 (swap 2 and 2)
3	Check nums[mid]=2, swap nums[mid] and nums[high], high--	0	0	5	[0,0,2,1,1,0,2,2]	Swap nums[0]<->nums[6], high=5	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
4	Check nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	1	1	5	[0,0,2,1,1,0,2,2]	Swap nums[0]<->nums[0], low=1, mid=1	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
5	Check nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	2	2	5	[0,0,2,1,1,0,2,2]	Swap nums[1]<->nums[1], low=2, mid=2	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
6	Check nums[mid]=2, swap nums[mid] and nums[high], high--	2	2	4	[0,0,0,1,1,2,2,2]	Swap nums[2]<->nums[5], high=4	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
7	Check nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	3	3	4	[0,0,0,1,1,2,2,2]	Swap nums[2]<->nums[2], low=3, mid=3	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
8	Check nums[mid]=1, mid++	3	4	4	[0,0,0,1,1,2,2,2]	mid=4	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
9	Check nums[mid]=1, mid++	3	5	4	[0,0,0,1,1,2,2,2]	mid=5	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
10	mid > high, done	3	5	4	[0,0,0,1,1,2,2,2]	End	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2

💡 mid (5) > high (4), sorting complete

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
low	0	0	0	1	2	2	3	3	3	3	3
mid	0	0	0	1	2	2	3	4	5	5	5
high	7	6	5	5	5	4	4	4	4	4	4
nums	[2,0,2,1,1,0,0,2]	[2,0,2,1,1,0,0,2]	[0,0,2,1,1,0,2,2]	[0,0,2,1,1,0,2,2]	[0,0,2,1,1,0,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]

Key Moments - 3 Insights

Why do we not increment mid when swapping with high pointer?

Because the element swapped from high to mid is unprocessed, we must check it again. See steps 2,3,6 where mid stays the same after swapping with high.

Why do we increment both low and mid when swapping 0?

Because after swapping 0 to the front, both low and mid move forward as the swapped elements are confirmed sorted. See steps 4,5,7.

What stops the loop?

The loop stops when mid pointer passes high pointer, meaning all elements are processed. See step 10 where mid=5 > high=4.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the array state?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 6 in execution_table.

At which step does the mid pointer first move past the high pointer?

A Step 10

B Step 9

C Step 8

D Step 7

💡 Hint

Look at 'mid' and 'high' values in execution_table rows; mid > high at step 10.

If the initial array had no 2s, how would the pointer 'high' behave?

A It would move to the start immediately.

B It would stay at the end and never move.

C It would move forward with mid.

D It would move backward only when swapping 0s.

💡 Hint

Since 'high' only moves when swapping 2s, no 2s means no swaps with high pointer.

Concept Snapshot

Sort Colors (Dutch Flag) uses three pointers: low, mid, high.
- low and mid start at 0, high at end.
- If nums[mid]==0: swap with nums[low], low++, mid++
- If nums[mid]==1: mid++
- If nums[mid]==2: swap with nums[high], high-- (mid stays)
- Loop ends when mid > high.
This sorts 0s,1s,2s in one pass efficiently.

Full Transcript

This visualization shows the Sort Colors algorithm using the Dutch Flag approach. We start with three pointers: low, mid at the start, and high at the end of the array. We check the element at mid. If it is 0, we swap it with the element at low and move both pointers forward. If it is 1, we just move mid forward. If it is 2, we swap it with the element at high and move high backward, but keep mid to check the swapped element. We repeat this until mid passes high. The execution table tracks each step, showing pointer positions and array state. Key moments clarify why mid does not move after swapping with high and when the loop ends. The quiz tests understanding of array states and pointer movements. This method sorts colors in one pass with constant space.

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