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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on Array

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

DSA Javascript

function dutchFlagPartition(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(dutchFlagPartition([2, 0, 2, 1, 1, 0], 1));

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

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

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

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

💡 Hint

Think about how the algorithm moves elements less than, equal to, and greater than the pivot.

The Dutch National Flag algorithm partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. The final array is 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 points to the last element greater than the pivot.

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

C It scans the array and decides whether to swap elements or move forward based on comparison with the pivot.

D It is used to swap elements greater than the pivot to the front.

💡 Hint

Consider how the algorithm processes each element one by one.

The 'mid' pointer scans the array from start to end, deciding whether to swap elements or move forward depending on their relation to the pivot.

🔧 Debug

advanced

Identify the Bug in Dutch National Flag Implementation

What error will the following code produce when run, and why?

DSA Javascript

function dutchFlagPartition(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(dutchFlagPartition([1, 0, 1, 1, 1, 0], 1));

A The code throws a TypeError due to invalid swap syntax.

B The code causes an infinite loop because 'mid' never increments.

C The code runs correctly and outputs [0, 0, 1, 1, 2, 2].

D The loop condition 'mid < high' causes the last elements to be skipped, resulting in incorrect partitioning.

💡 Hint

Check the loop condition carefully and think about when the loop stops.

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

❓ Predict Output

advanced

Result of Partitioning with Different Pivot

What is the output of the following code when partitioning the array around pivot value 2?

DSA Javascript

function dutchFlagPartition(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(dutchFlagPartition([3, 2, 1, 2, 3, 1, 2], 2));

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

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

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

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

💡 Hint

Remember the order: less than pivot, equal to pivot, greater than pivot.

The algorithm rearranges the array so that all elements less than 2 come first, then all 2s, then all elements greater than 2.

🧠 Conceptual

expert

Time Complexity of Dutch National Flag Algorithm

What is the time complexity of the Dutch National Flag algorithm when partitioning an array of size n?

A O(n) because each element is visited at most once.

B O(n log n) because it uses sorting internally.

C O(n^2) because of nested loops.

D O(log n) because it divides the array recursively.

💡 Hint

Think about how many times each element is processed.

The algorithm uses three pointers and processes each element once, resulting in linear time complexity.

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