Dutch National Flag Three Way Partition in DSA Typescript - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Initialize pointers: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Check arr[mid

↓

Swap arr[low

↓

low++, mid++

↩Back to Check mid <= high?

The algorithm uses three pointers to partition the array into three parts: 0s, 1s, and 2s by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA Typescript

function dutchFlagPartition(arr: number[]): void {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] === 0) {
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      low++; mid++;
    } else if (arr[mid] === 1) {
      mid++;
    } else {
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    }
  }
}

This code partitions the array so that all 0s come first, then 1s, then 2s using three pointers and swaps.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Initialize pointers	0	0	7	[2, 0, 2, 1, 1, 0, 0, 2]	low=0, mid=0, high=7
2	arr[mid]=2, swap arr[mid] and arr[high]	0	0	6	[2, 0, 2, 1, 1, 0, 0, 2]	Swap arr[0]<->arr[7], high=6
3	After swap	0	0	6	[2, 0, 2, 1, 1, 0, 0, 2]	Array unchanged visually, high decremented
4	arr[mid]=2, swap arr[mid] and arr[high]	0	0	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[0]<->arr[6], high=5
5	After swap	0	0	5	[0, 0, 2, 1, 1, 0, 2, 2]	Array updated, high decremented
6	arr[mid]=0, swap arr[low] and arr[mid]	0	0	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[0]<->arr[0], low=1, mid=1
7	After swap	1	1	5	[0, 0, 2, 1, 1, 0, 2, 2]	low and mid incremented
8	arr[mid]=0, swap arr[low] and arr[mid]	1	1	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[1]<->arr[1], low=2, mid=2
9	After swap	2	2	5	[0, 0, 2, 1, 1, 0, 2, 2]	low and mid incremented
10	arr[mid]=2, swap arr[mid] and arr[high]	2	2	5	[0, 0, 0, 1, 1, 2, 2, 2]	Swap arr[2]<->arr[5], high=4
11	After swap	2	2	4	[0, 0, 0, 1, 1, 2, 2, 2]	Array updated, high decremented
12	arr[mid]=0, swap arr[low] and arr[mid]	2	2	4	[0, 0, 0, 1, 1, 2, 2, 2]	Swap arr[2]<->arr[2], low=3, mid=3
13	After swap	3	3	4	[0, 0, 0, 1, 1, 2, 2, 2]	low and mid incremented
14	arr[mid]=1, mid++	3	3	4	[0, 0, 0, 1, 1, 2, 2, 2]	mid=4
15	arr[mid]=1, mid++	3	4	4	[0, 0, 0, 1, 1, 2, 2, 2]	mid=5
16	mid=5 > high=4, exit loop	3	5	4	[0, 0, 0, 1, 1, 2, 2, 2]	Loop ends

💡 mid (5) > high (4), so partitioning is complete

Variable Tracker

Variable	Start	After Step 6	After Step 9	After Step 13	Final
low	0	2	3	3	3
mid	0	2	3	5	5
high	7	5	5	4	4
Array	[2,0,2,1,1,0,0,2]	[0,0,2,1,1,0,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]

Key Moments - 3 Insights

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

Because after swapping with high, the new element at mid is unprocessed. We must check it again, as shown in steps 2-5 in the execution_table.

Why do we increment both low and mid when swapping with low pointer?

Because swapping with low moves a 0 to the front, which is correctly placed, so we can safely move both pointers forward. See steps 6-9.

What stops the loop from running infinitely?

The loop condition mid <= high ensures termination. Each step either increments mid or decrements high, moving pointers closer. See step 16 exit note.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what are the values of low and mid after the operation?

A low=0, mid=1

B low=1, mid=0

C low=1, mid=1

D low=0, mid=0

💡 Hint

Check the Pointer Changes column at step 6 in execution_table

At which step does the mid pointer first move past the high pointer, ending the loop?

A Step 15

B Step 16

C Step 14

D Step 13

💡 Hint

Look at the exit_note and Step column in execution_table

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

A mid would increment until it passes high without swaps

B mid would swap with low pointer

C mid would swap with high pointer

D mid would stay at 0

💡 Hint

Refer to the 'arr[mid] === 1' case in the code and execution_table steps 14-15

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- low and mid start at 0, high at end
- While mid <= high:
  - If arr[mid] == 0: swap with arr[low], low++, mid++
  - If arr[mid] == 1: mid++
  - If arr[mid] == 2: swap with arr[high], high--
- Result: all 0s, then 1s, then 2s in array

Full Transcript

The Dutch National Flag algorithm partitions an array containing 0s, 1s, and 2s into three sections. It uses three pointers: low, mid, and high. Initially, low and mid start at the beginning, and high at the end of the array. The algorithm checks the element at mid. If it is 0, it swaps with low and increments both low and mid. If it is 1, it just increments mid. If it is 2, it swaps with high and decrements high. This continues until mid passes high. The execution table shows each step, pointer positions, and array state. Key moments clarify why mid is not incremented after swapping with high and why the loop ends. The visual quiz tests understanding of pointer movements and loop termination.

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To reverse the elements of an array

B. To sort an array in ascending order using quicksort

C. To rearrange an array into three parts: less than, equal to, and greater than a pivot

D. To find the maximum element in an array

Solution

1. Step 1: Understand the algorithm's purpose and partitioning criteria

   The Dutch National Flag algorithm partitions an array into three parts based on a pivot value. It separates elements less than, equal to, and greater than the pivot.

2. Final Answer:

   To rearrange an array into three parts: less than, equal to, and greater than a pivot -> Option C

3. Quick Check:

   Partitioning = Rearranging into three parts [OK]

Hint: Remember: three parts based on pivot comparison [OK]

Common Mistakes:

• Confusing it with full sorting algorithms
• Thinking it only separates two parts
• Assuming it finds max or min values

2. Which of the following is the correct TypeScript syntax to swap two elements arr[i] and arr[j] in an array?

easy

A. const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Understand swapping in TypeScript and verify correct code

   TypeScript does not support tuple unpacking like Python, so use a temporary variable. const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; ensures correct swap.

2. Final Answer:

   const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

3. Quick Check:

   Temporary variable swap = const temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; [OK]

Hint: Use a temp variable to swap two elements safely [OK]

Common Mistakes:

• Using Python-style tuple unpacking syntax
• Overwriting one element before saving it
• Calling undefined swap functions

3. What will be the output array after applying the Dutch National Flag algorithm on arr = [2, 0, 2, 1, 1, 0] with pivot = 1?

medium

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

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

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

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

Solution

1. Step 1: Partition elements and arrange array

   Elements less than 1: 0, 0; equal to 1: 1, 1; greater than 1: 2, 2. Arrange as [less than] + [equal] + [greater than]: [0, 0, 1, 1, 2, 2].

2. Final Answer:

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

3. Quick Check:

   Partitioned array = [0, 0, 1, 1, 2, 2] [OK]

Hint: Group by less, equal, greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Assuming full sort instead of partition

4. Given this TypeScript code snippet for Dutch National Flag partition, what is the bug?

function dnfPartition(arr: number[], pivot: number): void {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] < pivot) {
      const temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
      low++;
    } else if (arr[mid] === pivot) {
      mid++;
    } else {
      const temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
      high--;
    }
  }
}

medium

A. Missing increment of mid after swapping when arr[mid] < pivot

B. Incorrect comparison operators used

C. Should decrement low instead of increment

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

Solution

1. Step 1: Analyze the swap when arr[mid] < pivot and identify effect

   After swapping arr[low] and arr[mid], low++ but missing mid++, causing the loop to recheck the same mid index, leading to infinite loop or wrong behavior.

2. Final Answer:

   Missing increment of mid after swapping when arr[mid] < pivot -> Option A

3. Quick Check:

   mid++ needed after swap when arr[mid] < pivot [OK]

Hint: Always increment mid after swapping with low [OK]

Common Mistakes:

• Forgetting to increment mid after swap
• Changing loop condition incorrectly
• Misusing comparison operators

5. You have an array arr = [3, 5, 2, 1, 4, 3, 2] and want to partition it using the Dutch National Flag algorithm with pivot = 3. After partitioning, which of the following is a valid output?

hard

A. [3, 3, 1, 2, 2, 4, 5]

B. [1, 2, 2, 3, 3, 4, 5]

C. [2, 1, 3, 2, 3, 4, 5]

D. [1, 2, 2, 4, 5, 3, 3]

Solution

1. Step 1: Identify groups based on pivot 3 and check options

   Less than 3: 1, 2, 2; equal to 3: 3, 3; greater than 3: 4, 5. Valid output must have all less, then all equal, then all greater.
   A: [1, 2, 2, 3, 3, 4, 5] valid.
   B: equals first, invalid.
   C: [2, 1, 3, 2, 3, 4, 5] has 2 (<3) after 3's, invalid.
   D: greater before equals, invalid.

2. Final Answer:

   [1, 2, 2, 3, 3, 4, 5] -> Option B

3. Quick Check:

   Partition order: less, equal, greater [OK]

Hint: Partition order must be less, equal, then greater [OK]

Common Mistakes:

• Placing equal elements at wrong position
• Confusing full sort with partition
• Ignoring group order rules