Dutch National Flag Three Way Partition in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on a sample array

What is the output of the following TypeScript code that partitions the array around the pivot value 2 using the Dutch National Flag algorithm?

DSA Typescript

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

const input = [3, 2, 1, 2, 3, 1, 2];
console.log(dutchNationalFlagPartition(input, 2));

A [1, 1, 2, 2, 2, 3, 3]

B [1, 2, 1, 2, 3, 2, 3]

C [3, 3, 2, 2, 2, 1, 1]

D [2, 2, 2, 1, 1, 3, 3]

💡 Hint

Remember the algorithm moves elements less than pivot to the front, equal in the middle, and greater to the end.

The Dutch National Flag algorithm partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. After processing, the array becomes sorted in that order.

🧠 Conceptual

intermediate

Understanding pointers in Dutch National Flag algorithm

In the Dutch National Flag algorithm, what is the role of the 'mid' pointer during the partitioning process?

A It marks the boundary between elements less than pivot and equal to pivot.

B It marks the boundary between elements equal to pivot and greater than pivot.

C It scans through the array to examine each element and decide its position.

D It points to the last element in the array.

💡 Hint

Think about which pointer moves through the array checking elements.

The 'mid' pointer moves from start to end, examining each element to decide if it should be swapped to the front, left in place, or swapped to the end.

🔧 Debug

advanced

Identify the bug in this Dutch National Flag implementation

What error will occur when running this TypeScript code for Dutch National Flag partition?

DSA Typescript

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

console.log(dnfPartition([3, 2, 1, 2, 3, 1, 2], 2));

A The function runs correctly and outputs the expected partitioned array.

B The swap syntax is invalid and causes a syntax error.

C The function throws a runtime error due to accessing out-of-bound indices.

D The loop condition 'mid < high' causes some elements to be skipped, resulting in incorrect partition.

💡 Hint

Check the loop condition carefully and think about when the loop should stop.

The loop should run while mid <= high to ensure all elements are processed. Using mid < high skips the last element, causing incorrect partition.

🚀 Application

advanced

Applying Dutch National Flag to sort colors

Given an array representing colors coded as 0 (red), 1 (white), and 2 (blue), which option shows the array after applying Dutch National Flag partition with pivot 1?

DSA Typescript

const colors = [2, 0, 2, 1, 1, 0];
function sortColors(arr: number[]): number[] {
  let low = 0, mid = 0, high = arr.length - 1;
  while (mid <= high) {
    if (arr[mid] < 1) {
      [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--;
    }
  }
  return arr;
}
console.log(sortColors(colors));

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

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

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

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

💡 Hint

The algorithm sorts elements less than pivot first, then equal, then greater.

The array is sorted so that all 0s come first, then 1s, then 2s, resulting in [0, 0, 1, 1, 2, 2].

🧠 Conceptual

expert

Why Dutch National Flag algorithm is efficient for three-way partitioning?

Which statement best explains why the Dutch National Flag algorithm is efficient for partitioning arrays into three parts?

A It uses three pointers and swaps elements in a single pass, avoiding multiple scans or extra space.

B It sorts the array completely using comparison-based sorting in O(n log n) time.

C It uses recursion to divide the array into smaller parts and merge them.

D It creates three separate arrays for each partition and concatenates them at the end.

💡 Hint

Think about how many times the array is scanned and if extra memory is used.

The algorithm uses three pointers to rearrange elements in one pass without extra arrays, making it efficient.

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