Dutch National Flag Three Way Partition in DSA Typescript - Build from Scratch

Dutch National Flag Three Way Partition

📖 Scenario: Imagine you have a box of colored balls represented by numbers: 0 for red, 1 for white, and 2 for blue. You want to sort them so that all reds come first, then whites, and then blues, just like the Dutch flag.

🎯 Goal: You will write a program to rearrange an array of numbers containing only 0s, 1s, and 2s so that all 0s come first, then all 1s, and then all 2s.

📋 What You'll Learn

Create an array called colors with the exact values [2, 0, 2, 1, 1, 0].

Create a variable called low and set it to 0.

Create a variable called mid and set it to 0.

Create a variable called high and set it to the last index of the colors array.

Use a while loop with the condition mid <= high.

Inside the loop, use if, else if, and else to check the value at colors[mid] and swap elements accordingly to sort the array.

Print the sorted colors array.

💡 Why This Matters

🌍 Real World

Sorting objects or items into three categories quickly, such as sorting balls by color or sorting tasks by priority.

💼 Career

Understanding this algorithm helps in interviews and real-world problems where efficient sorting or partitioning is needed.

1

Create the initial array

Create an array called colors with these exact values: [2, 0, 2, 1, 1, 0].

DSA Typescript

# Create the array colors with the given values
// Your code here

Hint

Use const colors = [2, 0, 2, 1, 1, 0]; to create the array.

2

Set up pointers for partitioning

Create variables called low and mid and set both to 0. Create a variable called high and set it to the last index of the colors array.

DSA Typescript

const colors = [2, 0, 2, 1, 1, 0];
// Create variables low, mid, and high as described
// Your code here

Hint

Use let low = 0;, let mid = 0;, and let high = colors.length - 1;.

3

Implement the Dutch National Flag partition logic

Use a while loop with the condition mid <= high. Inside the loop, use if, else if, and else to check the value at colors[mid]. If it is 0, swap colors[low] and colors[mid], then increment low and mid. If it is 1, just increment mid. If it is 2, swap colors[mid] and colors[high], then decrement high.

DSA Typescript

const colors = [2, 0, 2, 1, 1, 0];
let low = 0;
let mid = 0;
let high = colors.length - 1;

// Add the while loop and partition logic below
// Your code here

Hint

Use a while loop and swap elements based on the value at colors[mid].

4

Print the sorted array

Print the colors array after sorting using console.log(colors).

DSA Typescript

const colors = [2, 0, 2, 1, 1, 0];
let low = 0;
let mid = 0;
let high = colors.length - 1;

while (mid <= high) {
    if (colors[mid] === 0) {
        [colors[low], colors[mid]] = [colors[mid], colors[low]];
        low++;
        mid++;
    } else if (colors[mid] === 1) {
        mid++;
    } else {
        [colors[mid], colors[high]] = [colors[high], colors[mid]];
        high--;
    }
}

// Print the sorted colors array
// Your code here

Hint

Use console.log(colors); to print the sorted array.

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