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

Concept Flow - Sort Colors Two Pointer Dutch Flag

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

↓

Check nums[mid

↓

Swap nums[low

↓

low++, mid++

↓

high--

↓

Repeat until mid > high

↓

Done

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

Execution Sample

DSA Go

nums := []int{2,0,2,1,1,0}
low, mid, high := 0, 0, len(nums)-1
for mid <= high {
  switch nums[mid] {
  case 0: swap(nums, low, mid); low++; mid++
  case 1: mid++
  case 2: swap(nums, mid, high); high--
  }
}

Sorts the array nums containing 0,1,2 by moving 0s to front, 2s to end, and 1s stay in middle using two pointers.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2,0,2,1,1,0]	low=0, mid=0, high=5
2	nums[mid]=2, swap nums[mid] and nums[high]	0	0	5	[0,0,2,1,1,2]	Swap indices 0 and 5; high=5->4
3	After swap, nums[mid]=0, swap nums[low] and nums[mid]	0	0	4	[0,0,2,1,1,2]	Swap indices 0 and 0; low=0->1, mid=0->1
4	nums[mid]=0, swap nums[low] and nums[mid]	1	1	4	[0,0,2,1,1,2]	Swap indices 1 and 1; low=1->2, mid=1->2
5	nums[mid]=2, swap nums[mid] and nums[high]	2	2	4	[0,0,1,1,2,2]	Swap indices 2 and 4; high=4->3
6	After swap, nums[mid]=1, mid++	2	2	3	[0,0,1,1,2,2]	mid=2->3
7	nums[mid]=1, mid++	2	3	3	[0,0,1,1,2,2]	mid=3->4
8	mid=4 > high=3, stop	2	4	3	[0,0,1,1,2,2]	Done

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	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 after swapping with high when nums[mid] == 2?

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

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

Because swapping nums[low] and nums[mid] places a 0 at the front, so low moves forward. Also, mid moves forward to check the next element. See steps 3 and 4.

When does the loop stop?

The loop stops when mid passes high, meaning all elements after high are sorted 2s, and all before low are sorted 0s. See step 8.

Visual Quiz - 3 Questions

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

A 4

B 3

C 5

D 2

💡 Hint

Check the 'Pointer Changes' column at step 5 in execution_table.

At which step does mid first increment without swapping?

A Step 3

B Step 4

C Step 6

D Step 2

💡 Hint

Look for a step where nums[mid] == 1 and mid increments only.

If nums[mid] was 0 at step 2, what would happen to low and mid?

A Both low and mid increment

B Only mid increments

C Only low increments

D Neither increments

💡 Hint

Refer to the key_moments about incrementing low and mid when nums[mid] == 0.

Concept Snapshot

Sort Colors (Dutch Flag) uses three pointers: low, mid, high.
- low: boundary for 0s
- mid: current element
- high: boundary for 2s
Loop while mid <= high:
- 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
Stops when mid > high, array sorted in-place.

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 0, and high at the last index. 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. We repeat until mid passes high. The execution table tracks each step, showing the array state and pointer movements. Key moments clarify why mid is not always incremented after swaps with high and when the loop ends. The quiz tests understanding of pointer changes and loop behavior. This method sorts colors in one pass, in-place, efficiently.

Practice

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

easy

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

B. Sort the array using bubble sort repeatedly

C. Count each color and then overwrite the array

D. Use recursion to sort colors

Solution

1. Step 1: Understand the problem

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

2. Step 2: Identify the approach

   It uses three pointers (low, mid, high) to place 0s at the start, 2s at the end, and 1s in the middle in one pass.

3. Final Answer:

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

4. Quick Check:

   Three pointers = One pass sorting [OK]

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

Common Mistakes:

• Thinking it uses multiple passes like bubble sort
• Confusing counting approach with two-pointer method
• Assuming recursion is used

2. Which of the following Go code snippets correctly initializes the three pointers for the Dutch Flag algorithm?

easy

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

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

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

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

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Match initialization

   low, mid, high := 0, 0, len(nums)-1 correctly sets low=0, mid=0, high=len(nums)-1.

3. Final Answer:

   low, mid, high := 0, 0, len(nums)-1 -> Option A

4. Quick Check:

   Pointers start at array ends and start [OK]

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

Common Mistakes:

• Swapping low and high initialization
• Setting pointers outside array bounds
• Confusing mid pointer position

3. What will be the output of the following Go code after applying the Dutch Flag algorithm?

nums := []int{2, 0, 2, 1, 1, 0}
low, mid, high := 0, 0, len(nums)-1
for mid <= high {
  switch nums[mid] {
  case 0:
    nums[low], nums[mid] = nums[mid], nums[low]
    low++
    mid++
  case 1:
    mid++
  case 2:
    nums[mid], nums[high] = nums[high], nums[mid]
    high--
  }
}
fmt.Println(nums)

medium

A. [0 1 0 1 2 2]

B. [0 0 1 1 2 2]

C. [2 2 1 1 0 0]

D. [1 1 0 0 2 2]

Solution

1. Step 1: Trace the loop iterations

   Initially nums = [2,0,2,1,1,0], low=0, mid=0, high=5. The loop swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After processing, nums becomes [0,0,1,1,2,2].

3. Final Answer:

   [0 0 1 1 2 2] -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Not updating mid after swapping 0
• Updating mid after swapping 2 incorrectly
• Confusing order of swaps

4. Identify the bug in this Go code snippet implementing the Dutch Flag algorithm:

nums := []int{2,0,1}
low, mid, high := 0, 0, len(nums)-1
for mid < high {
  if nums[mid] == 0 {
    nums[low], nums[mid] = nums[mid], nums[low]
    low++
    mid++
  } else if nums[mid] == 2 {
    nums[mid], nums[high] = nums[high], nums[mid]
    high--
  } else {
    mid++
  }
}
fmt.Println(nums)

medium

A. Swapping 0s and 2s is done in wrong order

B. Pointers low and mid are initialized incorrectly

C. Loop condition should be mid <= high, not mid < high

D. The array is not initialized properly

Solution

1. Step 1: Check loop condition

   The loop uses 'mid < high' but it should be 'mid <= high' to process all elements including when mid equals high.

2. Step 2: Effect of wrong condition

   With 'mid < high', the last element may not be processed, causing incorrect sorting.

3. Final Answer:

   Loop condition should be mid <= high, not mid < high -> Option C

4. Quick Check:

   Loop must cover all elements [OK]

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

Common Mistakes:

• Using mid < high misses last element
• Incorrect pointer initialization
• Swapping logic errors

5. Given an array nums containing only 0s, 1s, and 2s, how would you modify the Dutch Flag algorithm to count the number of swaps performed during sorting?

hard

A. Count swaps after sorting by comparing original and sorted arrays

B. Swaps cannot be counted in this algorithm

C. Use recursion to count swaps automatically

D. Add a counter and increment it each time a swap occurs inside the loop

Solution

1. Step 1: Understand swap points

   Swaps happen when 0s or 2s are moved by exchanging elements inside the loop.

2. Step 2: Implement swap counter

   Introduce a variable initialized to 0 before the loop and increment it each time a swap statement executes.

3. Final Answer:

   Add a counter and increment it each time a swap occurs inside the loop -> Option D

4. Quick Check:

   Count swaps during execution [OK]

Hint: Increment counter on every swap inside loop [OK]

Common Mistakes:

• Counting swaps after sorting by comparing arrays
• Thinking recursion counts swaps automatically
• Assuming swaps cannot be tracked