Sort Colors Two Pointer Dutch Flag in DSA Java - 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 Java

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 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	Initialize pointers	0	0	5	[2,0,2,1,1,0]	low=0, mid=0, high=5	2 0 2 1 1 0
2	Check nums[mid]=2, swap nums[mid] and nums[high], high--	0	0	4	[0,0,2,1,1,2]	swap(0,5), high=4	0 0 2 1 1 2
3	Check nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	1	1	4	[0,0,2,1,1,2]	swap(0,0), low=1, mid=1	0 0 2 1 1 2
4	Check nums[mid]=0, swap nums[low] and nums[mid], low++, mid++	2	2	4	[0,0,2,1,1,2]	swap(1,1), low=2, mid=2	0 0 2 1 1 2
5	Check nums[mid]=2, swap nums[mid] and nums[high], high--	2	2	3	[0,0,1,1,2,2]	swap(2,4), high=3	0 0 1 1 2 2
6	Check nums[mid]=1, mid++	2	3	3	[0,0,1,1,2,2]	mid=3	0 0 1 1 2 2
7	Check nums[mid]=1, mid++	2	4	3	[0,0,1,1,2,2]	mid=4	0 0 1 1 2 2
8	mid > high, loop ends	2	4	3	[0,0,1,1,2,2]	end	0 0 1 1 2 2

💡 Loop ends when mid (4) > high (3), array is sorted.

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 swap nums[mid] with nums[high] and not increment mid when nums[mid] == 2?

Because after swapping with nums[high], the new nums[mid] might be 0,1 or 2, so we must check it again before moving mid. See step 5 where mid stays at 2 after swap.

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 next element. See steps 3 and 4.

When does the loop stop and why?

The loop stops when mid > high, meaning all elements beyond high are sorted as 2s, and all before low are 0s, so the middle are 1s. See step 8.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'high' after step 5?

A 4

B 3

C 5

D 2

💡 Hint

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

At which step does 'mid' first increment without swapping?

A Step 3

B Step 2

C Step 6

D Step 5

💡 Hint

Look for operation 'mid++' without swap in execution_table rows.

If the initial array started with all 1s, how would the pointer 'mid' move?

A mid would increment until it passes high without swaps

B mid would swap with low repeatedly

C mid would swap with high repeatedly

D mid would stay at 0 and loop infinitely

💡 Hint

Refer to the logic in execution_sample where nums[mid]==1 causes mid++ only.

Concept Snapshot

Sort Colors (0,1,2) using three pointers:
- low: boundary for 0s
- mid: current element
- high: boundary for 2s
Loop while mid <= high:
- if nums[mid]==0: swap with nums[low], low++, mid++
- if nums[mid]==1: mid++
- if nums[mid]==2: swap with nums[high], high--
This sorts in one pass, O(n) time, O(1) space.

Full Transcript

This visualization shows the Sort Colors problem solved by the Dutch National Flag algorithm using two pointers low and high, and a current pointer mid. Initially, low and mid start at 0, high at the last index. We check the element at mid: if 0, swap with low and move both pointers forward; if 1, just move mid forward; if 2, swap with high and move high backward without moving mid to recheck swapped element. The loop ends when mid passes high, ensuring all 0s are at front, 2s at end, and 1s in middle. The execution table traces each step with pointer positions and array state, clarifying how the array transforms. Key moments address why mid doesn't move after swapping with high and when the loop stops. The quiz tests understanding of pointer movements and conditions. This method sorts colors 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 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 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 way to initialize the pointers for the Dutch Flag algorithm in Java?

easy

A. int low = 0, mid = 0, high = 0;

B. int low = arr.length - 1, mid = 0, high = 0;

C. int low = 0, mid = arr.length - 1, high = 0;

D. int low = 0, mid = 0, high = arr.length - 1;

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Match initialization with roles

   int low = 0, mid = 0, high = arr.length - 1; correctly sets low and mid to 0, and high to last index (arr.length - 1).

3. Final Answer:

   int low = 0, mid = 0, high = arr.length - 1; -> Option D

4. Quick Check:

   Pointers start low=0, mid=0, high=end [OK]

Hint: Low and mid start at 0, high at array end [OK]

Common Mistakes:

• Setting pointers all to zero
• Starting high pointer at 0 instead of end
• Confusing mid and high initial positions

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

medium

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

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

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

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

Solution

1. Step 1: Apply Dutch Flag sorting logic

   Start with low=0, mid=0, high=5. Swap 2 with 0 at low, move pointers accordingly to group 0s, then 1s, then 2s.

2. Step 2: Final sorted array

   After sorting, the array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: 0s first, then 1s, then 2s after sorting [OK]

Common Mistakes:

• Not swapping correctly
• Mixing order of 1s and 2s
• Assuming original order stays same

4. Identify the error in this Java code snippet for the Dutch Flag algorithm:

int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
  if (arr[mid] == 0) {
    swap(arr, low, mid);
    low++;
  } else if (arr[mid] == 1) {
    mid++;
  } else {
    swap(arr, mid, high);
    high--;
  }
}

medium

A. Swap function parameters are wrong

B. Incorrect condition in while loop

C. Missing increment of mid pointer after swapping 0

D. No error, code is correct

Solution

1. Step 1: Analyze pointer increments after swaps

   When swapping 0, mid pointer must also increment to avoid infinite loop.

2. Step 2: Identify missing mid++ after swapping 0

   Code increments low but forgets to increment mid after swapping 0, causing repeated processing of same element.

3. Final Answer:

   Missing increment of mid pointer after swapping 0 -> Option C

4. Quick Check:

   mid++ needed after swapping 0 [OK]

Hint: Always increment mid after swapping 0 [OK]

Common Mistakes:

• Forgetting to increment mid after swap
• Changing while loop condition incorrectly
• Swapping wrong indices

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

hard

A. 6

B. 4

C. 5

D. 7

Solution

1. Step 1: Trace swaps during sorting

   Initial array: [1,2,0,2,1,0,0,2,1]. Swaps occur when 0 or 2 are moved. Counting swaps:
   - Swap 1: mid=1 (2) with high=8
   - Swap 2: mid=2 (0) with low=0
   - Swap 3: mid=3 (2) with high=7
   - Swap 4: mid=3 (2) with high=6
   - Swap 5: mid=3 (0) with low=1
   - Swap 6: mid=5 (0) with low=2

2. Step 2: Total swaps counted

   Total swaps performed are 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 move positions [OK]

Common Mistakes:

• Counting swaps only for 0s
• Ignoring swaps when swapping with same value
• Miscounting pointer moves as swaps