Dutch National Flag Three Way Partition in DSA Javascript

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.

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 all elements < 1 come first, then all == 1, then all > 1

Step 1: Check element at mid=0 (value 2), since 2 > 1, swap with element at high=6 and decrease high

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

Why: We move larger elements to the right side to keep partition correct

Step 2: Check element at mid=0 (value 2 again after swap), swap with element at high=5 and decrease high

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

Why: Still a large element, move it right

Step 3: Check element at mid=0 (value 2 again after swap), swap with element at high=4 and decrease high

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

Why: Still a large element, move it right

Step 4: Check element at mid=0 (value 2 again after swap), swap with element at high=3 and decrease high

2 0 1 1 2 0 2
low=0 mid=0 high=2

Why: Still a large element, move it right

Step 5: Check element at mid=0 (value 2 again after swap), swap with element at high=2 and decrease high

1 0 2 1 2 0 2
low=0 mid=0 high=1

Why: Still a large element, move it right

Step 6: Check element at mid=0 (value 1), since 1 == 1, just increase mid

1 0 2 1 2 0 2
low=0 mid=1 high=1

Why: Elements equal to pivot stay in the middle

Step 7: Check element at mid=1 (value 0), since 0 < 1, swap with element at low=0 and increase low and mid

0 1 2 1 2 0 2
low=1 mid=2 high=1

Why: Small elements go to the left side

Result:

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

Annotated Code

DSA Javascript

class DutchNationalFlag {
  static threeWayPartition(arr, pivot) {
    let low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
      if (arr[mid] < pivot) {
        [arr[low], arr[mid]] = [arr[mid], arr[low]]; // swap smaller to left
        low++;
        mid++;
      } else if (arr[mid] === pivot) {
        mid++; // equal stays in middle
      } else {
        [arr[mid], arr[high]] = [arr[high], arr[mid]]; // swap larger to right
        high--;
      }
    }
  }
}

// Driver code
const arr = [2, 0, 2, 1, 1, 0, 2];
DutchNationalFlag.threeWayPartition(arr, 1);
console.log(arr.join(' -> ') + ' -> null');

while (mid <= high) {

continue partitioning until mid passes high

if (arr[mid] < pivot) {

if current element is smaller, swap to left partition

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

swap smaller element to front

low++; mid++;

expand smaller and middle partitions

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

if element equals pivot, just move mid forward

mid++;

expand middle partition

else {

if element larger, swap to right partition

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

swap larger element to end

high--;

reduce right partition boundary

Output

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

Complexity Analysis

Time: O(n) because we scan the array once with constant swaps

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

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

Edge Cases

empty array

function completes immediately without changes

DSA Javascript

while (mid <= high) {

all elements equal to pivot

mid moves through entire array without swaps

DSA Javascript

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

all elements smaller or larger than pivot

elements get swapped to one side accordingly

DSA Javascript

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

When to Use This Pattern

When you need to sort or group an array into three parts around a pivot in one pass, use Dutch National Flag partition to do it efficiently.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high without checking the swapped element
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping elements incorrectly causing infinite loops
Fix: Always swap arr[mid] with arr[low] or arr[high] carefully and update pointers properly

Summary

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

Use when you want to partition arrays efficiently without full sorting, especially with three distinct groups.

The key is to maintain three pointers and swap elements to correct partitions while scanning once.

Practice

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

easy

A. To find the maximum element in an array

B. To sort an array in ascending order using quicksort

C. To reverse the elements of an array

D. To rearrange an array so that all elements less than a pivot come first, then equal elements, then greater elements

Solution

1. Step 1: Understand the partition goal

   The algorithm divides the array into three parts: less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Identify the rearrangement

   It rearranges elements so that all smaller come first, then equal, then larger, without full sorting.

3. Final Answer:

   To rearrange an array so that all elements less than a pivot come first, then equal elements, then greater elements -> Option D

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

Hint: Remember: three parts - less, equal, greater [OK]

Common Mistakes:

• Confusing partition with full sorting
• Thinking it only finds max or min
• Assuming it reverses the array

2. Which of the following is the correct way to initialize pointers for the Dutch National Flag algorithm in JavaScript?

easy

A. let low = 0, mid = 0, high = arr.length - 1;

B. let low = arr.length - 1, mid = 0, high = 0;

C. let low = 0, mid = arr.length - 1, high = 0;

D. let low = 0, mid = 1, high = arr.length;

Solution

1. Step 1: Identify pointer roles

   Low and mid start at 0, high at last index to cover full array.

2. Step 2: Match initialization to algorithm

   Correct initialization is low=0, mid=0, high=arr.length-1 to scan and partition properly.

3. Final Answer:

   let low = 0, mid = 0, high = arr.length - 1; -> Option A

4. Quick Check:

   Pointers start at array ends and middle [OK]

Hint: Start low and mid at 0, high at last index [OK]

Common Mistakes:

• Setting high to 0 instead of last index
• Starting mid at wrong position
• Using array length instead of length - 1

3. What will be the output of the following code snippet?

function dutchFlag(arr, pivot) {
  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(dutchFlag([2, 5, 1, 2, 3, 2, 4], 2));

medium

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

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

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

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

Solution

1. Step 1: Trace swaps for elements less than pivot

   Elements less than 2 (which is 1) move to front; 1 swaps to index 0.

2. Step 2: Place all 2s in middle and greater elements at end

   All 2s stay in middle; 3,4,5 move to the right side in any order preserving partition.

3. Final Answer:

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

4. Quick Check:

   Partitioned array with less, equal, greater [OK]

Hint: Swap less than pivot left, greater right [OK]

Common Mistakes:

• Not swapping correctly when element equals pivot
• Mixing order of greater elements
• Forgetting to increment mid after swap with low

4. Identify the bug in this Dutch National Flag partition code:

function partition(arr, pivot) {
  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;
}

medium

A. The pointers low and mid are initialized incorrectly

B. The while loop condition should be mid <= high, not mid < high

C. The swap operation is missing for elements equal to pivot

D. The high pointer should be incremented, not decremented

Solution

1. Step 1: Check loop condition correctness

   The loop must run while mid is less than or equal to high to process all elements.

2. Step 2: Identify impact of incorrect condition

   Using mid < high skips processing when mid equals high, missing last element check.

3. Final Answer:

   The while loop condition should be mid <= high, not mid < high -> Option B

4. Quick Check:

   Loop must cover all elements [OK]

Hint: Use mid <= high to cover all elements [OK]

Common Mistakes:

• Using mid < high causes last element to be skipped
• Incorrect pointer initialization
• Misunderstanding swap necessity for equal elements

5. Given an array [4, 9, 4, 7, 4, 8, 7] and pivot value 7, what will be the final array after applying the Dutch National Flag partition algorithm?

hard

A. [4, 4, 4, 7, 7, 8, 9]

B. [4, 4, 4, 7, 8, 7, 9]

C. [4, 4, 4, 7, 8, 9, 7]

D. [7, 7, 4, 4, 4, 8, 9]

Solution

1. Step 1: Partition elements less than pivot (7)

   All 4s move to the front: [4, 4, 4, ...]

2. Step 2: Place all 7s in the middle and greater elements at the end

   7s stay in the middle; 8 and 9 move to the right side in sorted order.

3. Final Answer:

   [4, 4, 4, 7, 7, 8, 9] -> Option A

4. Quick Check:

   Less, equal, greater partitioned correctly [OK]

Hint: Group less, equal, greater around pivot [OK]

Common Mistakes:

• Mixing order of greater elements
• Placing pivot elements incorrectly
• Not moving all less elements to front