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

↓

mid++

↓

Swap nums[mid

↓

Repeat loop

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

Execution Sample

DSA C

int low = 0, mid = 0, high = n - 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 array nums containing 0,1,2 by moving 0s left, 2s right, and 1s stay in middle using two pointers.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes	Visual State
1	Start	0	0	7	[2,0,2,1,1,0,0,2]	None	2 -> 0 -> 2 -> 1 -> 1 -> 0 -> 0 -> 2
2	nums[mid]=2, swap nums[mid] and nums[high], high--	0	0	6	[2,0,2,1,1,0,0,2]	Swap indices 0 and 7, high=6	2 -> 0 -> 2 -> 1 -> 1 -> 0 -> 0 -> 2
3	nums[mid]=2, swap nums[mid] and nums[high], high--	0	0	5	[0,0,2,1,1,0,2,2]	Swap indices 0 and 6, high=5	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
4	nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	1	1	5	[0,0,2,1,1,0,2,2]	Swap indices 0 and 0, low=1, mid=1	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
5	nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	2	2	5	[0,0,2,1,1,0,2,2]	Swap indices 1 and 1, low=2, mid=2	0 -> 0 -> 2 -> 1 -> 1 -> 0 -> 2 -> 2
6	nums[mid]=2, swap nums[mid] and nums[high], high--	2	2	4	[0,0,0,1,1,2,2,2]	Swap indices 2 and 5, high=4	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
7	nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	3	3	4	[0,0,0,1,1,2,2,2]	Swap indices 2 and 2, low=3, mid=3	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2
8	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	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	Check mid <= high? 5 <= 4 is False	3	5	4	[0,0,0,1,1,2,2,2]	Exit loop	0 -> 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2

💡 mid (5) > high (4), loop ends with array sorted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
low	0	0	0	1	2	2	3	3	3	3
mid	0	0	0	1	2	2	3	4	5	5
high	7	6	5	5	5	4	4	4	4	4
Array	[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]

Key Moments - 3 Insights

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

When nums[mid] is 2, we swap with nums[high] and decrement high but do not increment mid because the new nums[mid] after swap is unknown and must be checked again (see steps 2 and 3).

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

When nums[mid] is 0, swapping with nums[low] places 0 at the front, so we increment low and mid to move forward safely (see steps 4 and 5).

When does the loop stop?

The loop stops when mid passes high (step 10), meaning all elements are sorted with 0s before low, 1s between low and mid, and 2s after high.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what is the value of low and mid?

A low=2, mid=2

B low=1, mid=1

C low=0, mid=0

D low=3, mid=3

💡 Hint

Check the 'low' and 'mid' columns in execution_table row 5.

At which step does the condition mid <= high become false?

A Step 9

B Step 10

C Step 8

D Step 7

💡 Hint

Look at the exit_note and the last row in execution_table.

If we swapped nums[mid] and nums[high] but incremented mid immediately, what problem would occur?

A Low pointer would move incorrectly

B The array would be sorted faster

C We might skip checking the new nums[mid] which could be 0 or 2

D High pointer would increment instead of decrement

💡 Hint

Refer to key_moments explanation about why mid is not incremented after swapping with high.

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], increment low and mid.
- If nums[mid]==1, just increment mid.
- If nums[mid]==2, swap with nums[high], decrement high only.
- Loop ends when mid > high.
This sorts array in one pass with O(n) time and O(1) space.

Full Transcript

This visualization shows the Sort Colors problem solved by the Dutch National Flag algorithm using two pointers. We start with three pointers: low, mid at the beginning, 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 without moving mid, because the swapped element needs to be checked. We repeat this until mid passes high. The execution table shows each step with pointer positions and array state. Key moments clarify why mid is not incremented after swapping with high and when the loop ends. The quiz tests understanding of pointer values and loop termination. This method sorts the array in one pass efficiently.

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