Dutch National Flag Three Way Partition in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Typescript

function swap(arr: number[], i: number, j: number): void {
  const temp = arr[i];
  arr[i] = arr[[1]];
  arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

Ai

Bj

C0

Darr[j]

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of j causes no change.

Using arr[j] instead of index causes error.

We swap arr[i] with arr[j], so arr[i] = arr[j].

2fill in blank

medium

Complete the code to move the 'low' pointer forward after swapping.

DSA Typescript

if (arr[mid] < pivot) {
  swap(arr, low, mid);
  [1]++;
  mid++;
}

Drag options to blanks, or click blank then click option'

Ahigh

Bpivot

Cmid

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing mid twice causes skipping elements.

Incrementing pivot or high is incorrect here.

After swapping with low, we move low forward to next position.

3fill in blank

hard

Fix the error in the condition to check if element equals pivot.

DSA Typescript

else if (arr[mid] [1] pivot) {
  mid++;
}

Drag options to blanks, or click blank then click option'

A===

B=

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' causes assignment error.

Using '==' may cause unexpected type coercion.

Use '===' to check equality in TypeScript for value and type.

4fill in blank

hard

Fill both blanks to correctly move the 'high' pointer and swap elements greater than pivot.

DSA Typescript

else {
  swap(arr, mid, [1]);
  [2]--;
}

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

Clow

Dpivot

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'mid' instead of 'high' causes infinite loop.

Not decrementing 'high' pointer causes wrong partition.

Swap with 'high' pointer and then move 'high' backward.

5fill in blank

hard

Fill all three blanks to complete the main loop condition and pointer initialization.

DSA Typescript

let low = 0, mid = 0, high = arr.length [1] 1;
while (mid [2] high) {
  const pivot = arr[[3]];
  // partition logic here
}

Drag options to blanks, or click blank then click option'

A-

B<=

C0

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Setting high to length causes out-of-bounds error.

Using '>' instead of '<=' in loop condition skips elements.

High starts at last index (length - 1), loop runs while mid <= high, pivot is arr[0].

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