Sort Colors Two Pointer Dutch Flag in DSA Python - Execution Trace

Concept Flow - Sort Colors Two Pointer Dutch Flag

Start: Initialize pointers

↓

low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Check nums[mid

↓

Swap nums[low

↓

mid++

↓

Swap nums[mid

↓

Repeat Check mid <= high?

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

Execution Sample

DSA Python

nums = [2,0,2,1,1,0]
low = 0
mid = 0
high = len(nums) - 1
while mid <= high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1

Sorts the list nums containing 0,1,2 using three pointers in one pass.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2,0,2,1,1,0]	Initialize pointers
2	Check nums[mid]=2	0	0	5	[2,0,2,1,1,0]	Swap nums[mid] and nums[high], high--
3	Swap nums[0]<->nums[5]	0	0	4	[0,0,2,1,1,2]	high=5->4, mid stays 0
4	Check nums[mid]=0	0	0	4	[0,0,2,1,1,2]	Swap nums[low] and nums[mid], low++, mid++
5	Swap nums[0]<->nums[0]	1	1	4	[0,0,2,1,1,2]	low=0->1, mid=0->1
6	Check nums[mid]=0	1	1	4	[0,0,2,1,1,2]	Swap nums[low] and nums[mid], low++, mid++
7	Swap nums[1]<->nums[1]	2	2	4	[0,0,2,1,1,2]	low=1->2, mid=1->2
8	Check nums[mid]=2	2	2	4	[0,0,2,1,1,2]	Swap nums[mid] and nums[high], high--
9	Swap nums[2]<->nums[4]	2	2	3	[0,0,1,1,2,2]	high=4->3, mid stays 2
10	Check nums[mid]=1	2	2	3	[0,0,1,1,2,2]	mid++
11	mid=2->3	2	3	3	[0,0,1,1,2,2]	No swap
12	Check nums[mid]=1	2	3	3	[0,0,1,1,2,2]	mid++
13	mid=3->4	2	4	3	[0,0,1,1,2,2]	No swap
14	Check mid <= high? 4 <= 3	2	4	3	[0,0,1,1,2,2]	Condition false, stop

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
low	0	0	1	2	2	2	2	2
mid	0	0	1	2	2	3	4	4
high	5	4	4	4	3	3	3	3
nums	[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]	[0,0,1,1,2,2]

Key Moments - 3 Insights

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

Because after swapping with high, the new nums[mid] is unknown and must be checked again. See steps 2-3 and 8-9 where mid stays the same after swap.

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

Because swapping 0 to front ensures that position is sorted, so we can safely move both pointers forward. See steps 4-7 where low and mid both increment.

When does the loop stop?

The loop stops when mid passes high, meaning all elements beyond high are sorted as 2s. See step 14 where mid=4 > high=3.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

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

At which step does the mid pointer first increment without swapping?

A Step 10

B Step 2

C Step 6

D Step 4

💡 Hint

Look for steps where 'mid++' happens without swap in the 'Pointer Changes' column.

If we changed the first element from 2 to 1, what would happen at step 2?

A Swap with high pointer and decrement high

B Increment mid pointer only

C Swap with low pointer and increment low and mid

D Loop ends immediately

💡 Hint

Check the condition for nums[mid] == 1 in the code and execution_table steps.

Concept Snapshot

Sort Colors (0,1,2) using three pointers:
- low: next position for 0
- mid: current element
- high: next position for 2
Loop while mid <= high:
- If nums[mid]==0: swap with low, low++, mid++
- If nums[mid]==1: mid++
- If nums[mid]==2: swap with high, high--
One pass, in-place, O(n) time.

Full Transcript

This visualization shows how the Dutch National Flag algorithm sorts an array of 0s, 1s, and 2s using three pointers: low, mid, and high. Initially, low and mid start at the beginning, and high at the end. We check the element at mid: if it's 0, we swap it with low and move both pointers forward; if it's 1, we just move mid forward; if it's 2, we swap it with high and move high backward without moving mid, because the swapped element needs checking. This continues until mid passes high, ensuring all 0s are at front, 1s in middle, and 2s at end. The execution table tracks each step, pointer positions, and array state changes. Key moments clarify why mid doesn't always move after swapping with high and when the loop ends. The quiz tests understanding of pointer movements and array states during sorting.

Practice

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

easy

A. To reverse the elements of an array

B. To sort any array of integers in ascending order

C. To find the maximum element in an array

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

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 D

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 array, not just 0,1,2
• Confusing it with general sorting algorithms
• Assuming it requires multiple passes

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

easy

A. low, mid, high = 0, len(nums) - 1, 0

B. low, mid, high = 0, 0, len(nums) - 1

C. low, mid, high = len(nums) - 1, 0, 0

D. low, mid, high = len(nums) - 1, len(nums) - 1, 0

Solution

1. Step 1: Recall pointer roles

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

2. Step 2: Match initialization

   So, low = 0, mid = 0, high = len(nums) - 1 is correct.

3. Final Answer:

   low, mid, high = 0, 0, len(nums) - 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:

• Swapping high and mid initialization
• Starting pointers at wrong indices
• Using length instead of length-1 for high

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

nums = [2, 0, 2, 1, 1, 0]
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

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, 1, 0, 2, 2]

Solution

1. Step 1: Trace the algorithm on input

   Initially nums = [2,0,2,1,1,0]. The algorithm swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After the loop, nums becomes [0,0,1,1,2,2], sorted by color.

3. Final Answer:

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

4. Quick Check:

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

Hint: Remember: 0s front, 1s middle, 2s end [OK]

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing order of pointers

4. Identify the bug in the following Dutch Flag algorithm code:

nums = [2, 0, 1]
low, mid, high = 0, 0, len(nums) - 1
while mid < high:
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]
        low += 1
        mid += 1
    elif nums[mid] == 1:
        mid += 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high -= 1
print(nums)

medium

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

B. Pointers low and mid are initialized incorrectly

C. Swapping logic for nums[mid] == 0 is wrong

D. The decrement of high should be after incrementing mid

Solution

1. Step 1: Analyze loop condition

   The loop runs while mid < high, so it stops when mid == high, missing last element check.

2. Step 2: Correct loop condition

   It should be mid <= high to process all elements including when mid equals high.

3. Final Answer:

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

4. Quick Check:

   Loop must cover mid == high [OK]

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

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pointer initialization unnecessarily
• Incorrect swap logic for 0 or 2

5. Given an array nums = [1, 2, 0, 1, 2, 0, 1], how many swaps will the Dutch Flag algorithm perform to sort it?

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace swaps during sorting

   Initial: [1,2,0,1,2,0,1] low=0, mid=0, high=6
   - mid=0 (1): mid=1 (no swap)
   - mid=1 (2): swap(1,6) -> [1,1,0,1,2,0,2] high=5 (swap 1)
   - mid=1 (1): mid=2
   - mid=2 (0): swap(0,2) -> [0,1,1,1,2,0,2] low=1 mid=3 (swap 2)
   - mid=3 (1): mid=4
   - mid=4 (2): swap(4,5) -> [0,1,1,1,0,2,2] high=4 (swap 3)
   - mid=4 (0): swap(1,4) -> [0,0,1,1,1,2,2] low=2 mid=5 (swap 4)

2. Step 2: Total swaps counted

   There are 4 swaps in total during the process.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 moves happen [OK]

Common Mistakes:

• Counting pointer moves as swaps
• Missing swaps when swapping with same element
• Not tracing all pointer changes