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

Concept Flow - Sort Colors Two Pointer Dutch Flag

Start with array

↓

Initialize pointers: low=0, mid=0, high=end

↓

While mid <= high

↓

Check array[mid

↓

Swap with low

↓

Increment low, mid

↓

Repeat until mid > high

↓

Array sorted: 0s, then 1s, then 2s

This flow shows how two pointers (low and high) and a mid pointer move through the array to sort colors by swapping 0s to the front and 2s to the end, leaving 1s in the middle.

Execution Sample

DSA C#

int[] nums = {2,0,2,1,1,0};
int low = 0, mid = 0, high = nums.Length - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    Swap(nums, low++, mid++);
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    Swap(nums, mid, high--);
  }
}

Sorts the array of colors represented by 0,1,2 using three pointers to place 0s at start, 2s at end, and 1s in the middle.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes	Visual State
1	Start	0	0	5	[2,0,2,1,1,0]	None	low=0, mid=0, high=5
2	Check nums[mid]=2	0	0	5	[2,0,2,1,1,0]	Swap nums[mid] and nums[high], high--	Swap indices 0 and 5; high=4
3	After swap	0	0	4	[0,0,2,1,1,2]	None	Array updated, mid stays 0
4	Check nums[mid]=0	0	0	4	[0,0,2,1,1,2]	Swap nums[mid] and nums[low], low++, mid++	Swap indices 0 and 0; low=1, mid=1
5	After swap	1	1	4	[0,0,2,1,1,2]	None	Array unchanged visually
6	Check nums[mid]=0	1	1	4	[0,0,2,1,1,2]	Swap nums[mid] and nums[low], low++, mid++	Swap indices 1 and 1; low=2, mid=2
7	After swap	2	2	4	[0,0,2,1,1,2]	None	Array unchanged visually
8	Check nums[mid]=2	2	2	4	[0,0,2,1,1,2]	Swap nums[mid] and nums[high], high--	Swap indices 2 and 4; high=3
9	After swap	2	2	3	[0,0,1,1,2,2]	None	Array updated, mid stays 2
10	Check nums[mid]=1	2	2	3	[0,0,1,1,2,2]	mid++	mid=3
11	Check nums[mid]=1	2	3	3	[0,0,1,1,2,2]	mid++	mid=4
12	End condition mid=4 > high=3	2	4	3	[0,0,1,1,2,2]	Stop	Array sorted

💡 Loop ends when mid (4) is greater than high (3), meaning all elements are sorted.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
low	0	0	1	2	2	2	2
mid	0	0	1	2	2	3	4
high	5	4	4	4	3	3	3
Array	[2,0,2,1,1,0]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]

Key Moments - 3 Insights

Why does mid not increment after swapping with high when nums[mid] is 2?

Because after swapping with high, the new nums[mid] could be 0,1, or 2. We must check it again before moving mid forward. See steps 2-3 and 8-9 in the execution_table.

Why do we increment both low and mid when nums[mid] is 0?

Swapping nums[mid] with nums[low] places a 0 at the front, so low moves forward. Since the swapped element at mid is guaranteed to be 1 or 0, we can safely move mid forward too. See steps 4-6.

When does the loop stop and why?

The loop stops when mid becomes greater than high, meaning all elements beyond high are sorted as 2s, and all before low are 0s, with 1s in the middle. See step 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the value of 'high' after the swap?

A 2

B 3

C 4

D 5

💡 Hint

Check the 'high' column in execution_table row for step 8.

At which step does 'mid' first increment without a swap?

A Step 4

B Step 2

C Step 10

D Step 8

💡 Hint

Look for steps where operation is 'Check nums[mid]=1' and mid increments without swapping.

If the initial array started with all 0s, how would the 'low' pointer change after the first iteration?

A It would increment to 1

B It would stay at 0

C It would decrement

D It would jump to the end

💡 Hint

Refer to variable_tracker and key_moments about how low increments when nums[mid] is 0.

Concept Snapshot

Sort Colors (Dutch Flag) uses three pointers: low, mid, high.
- low: boundary for 0s
- mid: current element
- high: boundary for 2s
Traverse with mid:
- If 0: swap with low, increment low and mid
- If 1: just increment mid
- If 2: swap with high, decrement high
Stop when mid > high.
Result: 0s, then 1s, then 2s in order.

Full Transcript

This visualization shows the Sort Colors problem solved by the Dutch National Flag algorithm using two pointers low and high, and a mid pointer. The array is traversed with mid. When nums[mid] is 0, it swaps with nums[low] and both pointers move forward. When nums[mid] is 1, mid moves forward. When nums[mid] is 2, it swaps with nums[high] and high moves backward, but mid stays to re-check the swapped value. The process continues until mid passes high, ensuring the array is sorted with all 0s first, then 1s, then 2s. The execution table tracks each step, pointer positions, and array state. Key moments clarify why mid does not always move after swaps with high and when the loop ends. The quiz tests understanding of pointer changes and loop behavior.

Practice

1. What is the main idea behind the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. Swap elements randomly until sorted

B. Sort the array using built-in sort function

C. Count each color and then overwrite the array

D. Use three pointers to separate 0s, 1s, and 2s in one pass

Solution

1. Step 1: Understand the problem

   The algorithm sorts an array containing only 0s, 1s, and 2s representing colors.

2. Step 2: Use three pointers

   It uses three pointers: low, mid, and high to separate the colors in one pass efficiently.

3. Final Answer:

   Use three pointers to separate 0s, 1s, and 2s in one pass -> Option D

4. Quick Check:

   Three pointers = A [OK]

Hint: Remember three pointers separate colors in one pass [OK]

Common Mistakes:

• Using built-in sort instead of pointers
• Counting colors then rewriting array
• Swapping elements without pointers

2. Which of the following is the correct initialization of pointers in the Dutch Flag algorithm in C#?

easy

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

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

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

D. int low = 0, mid = 1, high = nums.Length;

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high starts at last index (length - 1).

2. Step 2: Check initialization correctness

   int low = 0, mid = 0, high = nums.Length - 1; correctly sets low and mid to 0, high to nums.Length - 1.

3. Final Answer:

   int low = 0, mid = 0, high = nums.Length - 1; -> Option A

4. Quick Check:

   Correct pointer init = C [OK]

Hint: Start low and mid at 0, high at last index [OK]

Common Mistakes:

• Setting high to 0 instead of last index
• Starting mid at length - 1
• Using invalid pointer values

3. What will be the output array after running the Dutch Flag algorithm on nums = new int[] {2, 0, 2, 1, 1, 0};?

medium

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

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

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

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

Solution

1. Step 1: Start with pointers low=0, mid=0, high=5

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

2. Step 2: Process elements using Dutch Flag logic

   Swap 2 with 0 at high, move high left; swap 2 with 0 at low; move mid and low accordingly until sorted.

3. Final Answer:

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

4. Quick Check:

   Sorted colors = A [OK]

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

Common Mistakes:

• Not swapping correctly
• Moving pointers incorrectly
• Confusing order of colors

4. Identify the bug in the following C# code snippet for the Dutch Flag algorithm:

int low = 0, mid = 0, high = nums.Length - 1;
while (mid <= high) {
  if (nums[mid] == 0) {
    Swap(nums, low, mid);
    low++;
  } else if (nums[mid] == 1) {
    mid++;
  } else {
    Swap(nums, mid, high);
    high--;
  }
}

medium

A. Swap function parameters are incorrect

B. Missing increment of mid after swapping 0

C. high should be incremented instead of decremented

D. mid should not be incremented when nums[mid] == 1

Solution

1. Step 1: Check pointer increments after swaps

   When nums[mid] == 0, after swapping with low, mid must also increment to avoid infinite loop.

2. Step 2: Identify missing mid++

   The code increments low but misses mid++, causing mid to stay and loop endlessly.

3. Final Answer:

   Missing increment of mid after swapping 0 -> Option B

4. Quick Check:

   Increment mid after 0 swap = D [OK]

Hint: Always increment mid after swapping 0 [OK]

Common Mistakes:

• Forgetting mid++ after swapping 0
• Decrementing high incorrectly
• Incorrect swap parameters

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch Flag algorithm to sort an array that also contains 3s, placing all 3s at the end?

hard

A. Add a fourth pointer and extend the logic to handle 3s at the end

B. Use the same three pointers but treat 3s as 2s

C. Sort the array normally using built-in sort for 3s

D. Ignore 3s since they are already at the end

Solution

1. Step 1: Understand limitation of three pointers

   The original algorithm handles only three values (0,1,2). Adding 3 requires extra handling.

2. Step 2: Introduce a fourth pointer

   Use four pointers to separate 0s, 1s, 2s, and 3s, extending the logic to place 3s at the end.

3. Final Answer:

   Add a fourth pointer and extend the logic to handle 3s at the end -> Option A

4. Quick Check:

   Four pointers for four colors = B [OK]

Hint: Add pointer per unique value for correct sorting [OK]

Common Mistakes:

• Treating 3s as 2s causing wrong order
• Using built-in sort instead of pointers
• Ignoring 3s placement