Dutch National Flag Three Way Partition in DSA Typescript

Mental Model

We rearrange an array into three parts: smaller than pivot, equal to pivot, and greater than pivot, all in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick each ball once and put it in the right bin without extra space.

[pivot=1]
Index: 0  1  2  3  4  5  6
Array: 2  0  2  1  1  0  2

Pointers:
low ↑    mid ↑          high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0, 2], pivot = 1

Goal: Rearrange array so that all elements < 1 come first, then elements == 1, then elements > 1

Step 1: Start with low=0, mid=0, high=6; check element at mid=0 (value=2)

[2] 0 2 1 1 0 2
low=0 mid=0 high=6

Why: We need to decide where 2 belongs; since 2 > pivot(1), swap with high

Step 2: Swap arr[mid]=2 with arr[high]=2; decrement high to 5; mid stays at 0

[2] 0 2 1 1 0 [2]
low=0 mid=0 high=5

Why: 2 is greater than pivot, so move it to the end; mid stays to check swapped element

Step 3: Check element at mid=0 (value=2) again

[2] 0 2 1 1 0 2
low=0 mid=0 high=5

Why: After swap, mid points to new element; must check it

Step 4: Swap arr[mid]=2 with arr[high]=0; decrement high to 4; mid stays at 0

[0] 0 2 1 1 [2] 2
low=0 mid=0 high=4

Why: 2 > pivot, so move it to the end; mid stays to check swapped element

Step 5: Check element at mid=0 (value=0)

[0] 0 2 1 1 2 2
low=0 mid=0 high=4

Why: 0 < pivot, so swap with low and move both pointers forward

Step 6: Swap arr[mid]=0 with arr[low]=0; increment low to 1 and mid to 1

0 [0] 2 1 1 2 2
low=1 mid=1 high=4

Why: 0 is less than pivot, so move it to the front

Step 7: Check element at mid=1 (value=0)

0 [0] 2 1 1 2 2
low=1 mid=1 high=4

Why: 0 < pivot, so swap with low and move both pointers forward

Step 8: Swap arr[mid]=0 with arr[low]=0; increment low to 2 and mid to 2

0 0 [2] 1 1 2 2
low=2 mid=2 high=4

Why: 0 is less than pivot, so move it to the front

Step 9: Check element at mid=2 (value=2)

0 0 [2] 1 1 2 2
low=2 mid=2 high=4

Why: 2 > pivot, swap with high

Step 10: Swap arr[mid]=2 with arr[high]=1; decrement high to 3; mid stays at 2

0 0 [1] 1 [2] 2 2
low=2 mid=2 high=3

Why: Move 2 to the end; mid stays to check swapped element

Step 11: Check element at mid=2 (value=1)

0 0 [1] 1 2 2 2
low=2 mid=2 high=3

Why: 1 == pivot, just move mid forward

Step 12: Increment mid to 3

0 0 1 [1] 2 2 2
low=2 mid=3 high=3

Why: Elements equal to pivot stay in the middle

Step 13: Check element at mid=3 (value=1)

0 0 1 [1] 2 2 2
low=2 mid=3 high=3

Why: 1 == pivot, move mid forward

Step 14: Increment mid to 4

0 0 1 1 2 2 2
low=2 mid=4 high=3

Why: mid passed high, done

Result:

0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2 -> null

Annotated Code

DSA Typescript

class DutchNationalFlag {
  static threeWayPartition(arr: number[], pivot: number): void {
    let low = 0;
    let mid = 0;
    let 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--;
      }
    }
  }
}

// Driver code
const arr = [2, 0, 2, 1, 1, 0, 2];
const pivot = 1;
DutchNationalFlag.threeWayPartition(arr, pivot);

// Print result
console.log(arr.join(' -> ') + ' -> null');

while (mid <= high) {

loop until mid passes high to cover all elements

if (arr[mid] < pivot) {

element less than pivot goes to front

[arr[low], arr[mid]] = [arr[mid], arr[low]];

swap element at mid with low to move smaller element forward

low++; mid++;

increment low and mid pointers after placing smaller element

else if (arr[mid] === pivot) {

element equal to pivot stays in middle, just move mid

mid++;

advance mid pointer

else {

element greater than pivot goes to end

[arr[mid], arr[high]] = [arr[high], arr[mid]];

swap element at mid with high to move larger element backward

high--;

decrement high pointer after placing larger element

Output

0 -> 0 -> 1 -> 1 -> 2 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we traverse the array once with mid pointer

Space: O(1) because partitioning is done in place without extra space

vs Alternative: Compared to sorting the whole array O(n log n), this is faster and uses no extra space

Edge Cases

empty array

function completes immediately without changes

DSA Typescript

while (mid <= high) {

all elements equal to pivot

mid pointer moves through entire array without swaps

DSA Typescript

else if (arr[mid] === pivot) {

all elements less than pivot

all elements swapped to front, low and mid move together

DSA Typescript

if (arr[mid] < pivot) {

all elements greater than pivot

all elements swapped to end, high pointer moves down

DSA Typescript

else {

When to Use This Pattern

When you need to sort or group elements into three categories around a pivot in one pass, use the Dutch National Flag pattern for efficient partitioning.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high when element is greater than pivot
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping elements incorrectly causing infinite loops or missed elements
Fix: Always swap with low or high pointers correctly and update pointers carefully

Summary

Rearranges an array into three parts: less than, equal to, and greater than a pivot in one pass.

Use when you want to partition data efficiently without full sorting.

The key is to use three pointers to track boundaries and swap elements in place.

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