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

↓

Repeat check mid <= high?

We use three pointers to separate 0s, 1s, and 2s by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA Javascript

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Sorts an array 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]	Initial pointers set
2	nums[mid]=2, swap nums[mid] and nums[high]	0	0	4	[0,0,2,1,1,2]	Swap mid(0) and high(5), high-- to 4
3	nums[mid]=0, swap nums[low] and nums[mid]	0	0	4	[0,0,2,1,1,2]	Swap low(0) and mid(0), low++ to 1, mid++ to 1
4	nums[mid]=0, swap nums[low] and nums[mid]	1	1	4	[0,0,2,1,1,2]	Swap low(1) and mid(1), low++ to 2, mid++ to 2
5	nums[mid]=2, swap nums[mid] and nums[high]	2	2	4	[0,0,1,1,2,2]	Swap mid(2) and high(4), high-- to 3
6	nums[mid]=1, mid++	2	2	3	[0,0,1,1,2,2]	mid++ to 3
7	nums[mid]=1, mid++	2	3	3	[0,0,1,1,2,2]	mid++ to 4
8	mid(4) > high(3), done	2	4	3	[0,0,1,1,2,2]	Sorting complete

💡 mid pointer passed high pointer, all elements 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 not increment mid after swapping with high when nums[mid] is 2?

Because after swapping with high, the new nums[mid] is unknown and must be checked again. See step 2 and 5 in execution_table where mid stays the same.

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

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

When does the loop stop?

The loop stops when mid pointer passes high pointer, meaning all elements are sorted. See step 8 where mid=4 > high=3.

Visual Quiz - 3 Questions

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

A 4

B 2

C 3

D 5

💡 Hint

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

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

A Step 6

B Step 3

C Step 2

D Step 4

💡 Hint

Look for steps where operation is 'nums[mid]=1, mid++' in execution_table.

If the initial array had no 2s, how would the pointer 'high' change?

A It would increment

B It would stay at the last index throughout

C It would decrement to zero

D It would move to mid

💡 Hint

Since swaps with high happen only when nums[mid] is 2, see variable_tracker for 'high' changes.

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.
- Repeat until mid > high.
This sorts array in one pass with O(n) time and O(1) space.

Full Transcript

The Sort Colors problem uses three pointers to separate 0s, 1s, and 2s in one pass. We start with low and 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. We repeat this until mid passes high, meaning all elements are sorted. This method is efficient and uses constant space. The execution table shows each step with pointer positions and array state. Key moments clarify why mid does not move after swapping with high and when the loop ends. The visual quiz tests understanding of pointer changes and loop behavior.

Practice

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

easy

A. To find the maximum value in an array

B. To sort any array of integers in ascending order

C. To reverse the elements of 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 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 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 integer array
• Confusing it with general sorting algorithms
• Assuming it reverses the array

2. Which of the following is the correct initialization for the two pointers in the Dutch Flag algorithm in JavaScript?

easy

A. let low = 0, mid = 0, high = nums.length - 1;

B. let low = 0, mid = nums.length - 1, high = 0;

C. let low = nums.length - 1, mid = 0, high = 0;

D. let low = nums.length - 1, mid = nums.length - 1, high = 0;

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 to roles

   Correct initialization is let low = 0, mid = 0, high = nums.length - 1;.

3. Final Answer:

   let low = 0, mid = 0, high = nums.length - 1; -> Option A

4. Quick Check:

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

Hint: Start low and mid at 0, high at array end [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 array after running the Dutch Flag algorithm on nums = [2, 0, 2, 1, 1, 0]?

medium

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

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

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

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

Solution

1. Step 1: Apply Dutch Flag sorting logic

   Sort 0s to front, 1s in middle, 2s at end in one pass.

2. Step 2: Result after sorting

   The sorted array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort 0s front, 1s middle, 2s end in one pass [OK]

Common Mistakes:

• Not sorting all 0s to front
• Mixing order of 1s and 2s
• Returning original unsorted array

4. Identify the bug in this snippet of the Dutch Flag algorithm:

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

medium

A. Incorrect comparison operator in while loop

B. Missing increment of mid after swapping 0s

C. Swapping 2s with low instead of high

D. No bug, code is correct

Solution

1. Step 1: Analyze pointer increments after swaps

   When swapping 0s, mid pointer must also move forward to avoid infinite loop.

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

   The code increments low but forgets to increment mid after swapping 0s.

3. Final Answer:

   Missing increment of mid after swapping 0s -> Option B

4. Quick Check:

   mid++ missing after 0 swap causes infinite loop [OK]

Hint: Increment mid after swapping 0s to avoid infinite loop [OK]

Common Mistakes:

• Forgetting mid++ after swapping 0s
• Swapping 2s with wrong pointer
• Incorrect loop condition

5. Given an array nums with values 0, 1, and 2, how would you modify the Dutch Flag algorithm to count how many swaps are performed during sorting?

hard

A. Use a separate array to track swaps

B. Count the number of 0s, 1s, and 2s before sorting

C. Add a counter variable and increment it each time a swap occurs

D. Increment a counter only when mid pointer moves

Solution

1. Step 1: Understand swap operations in algorithm

   Swaps happen when 0 or 2 is encountered and elements are exchanged.

2. Step 2: Track swaps with a counter

   Introduce a variable initialized to zero and increment it every time a swap line executes.

3. Final Answer:

   Add a counter variable and increment it each time a swap occurs -> Option C

4. Quick Check:

   Count swaps by incrementing counter on each swap [OK]

Hint: Increment counter inside swap blocks to count swaps [OK]

Common Mistakes:

• Counting pointer moves instead of swaps
• Counting elements instead of swaps
• Using extra arrays unnecessarily