Dutch National Flag Three Way Partition in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Dutch National Flag problem?

To rearrange an array with three distinct values so that all elements of the first value come first, followed by all elements of the second value, and then all elements of the third value.

beginner

Which three pointers are used in the Dutch National Flag algorithm?

Low (start of first section), Mid (current element), and High (end of third section).

intermediate

In the Dutch National Flag algorithm, what happens when the mid pointer points to the first value?

Swap the element at mid with the element at low, then increment both low and mid pointers.

intermediate

What is the time complexity of the Dutch National Flag algorithm?

O(n), where n is the number of elements in the array, because each element is processed at most once.

beginner

Why is the Dutch National Flag algorithm considered an in-place algorithm?

Because it rearranges the elements within the original array without using extra space for another array.

What does the 'mid' pointer represent in the Dutch National Flag algorithm?

A The start of the first section

B The current element being examined

C The end of the last section

D The pivot element

The 'mid' pointer scans through the array, examining each element to decide where it belongs.

When the element at 'mid' is the third value, what action is taken?

A Do nothing and move 'low'

B Swap with element at 'low' and increment both 'low' and 'mid'

C Increment 'mid' only

D Swap with element at 'high' and decrement 'high'

Elements equal to the third value are swapped with the element at 'high', and 'high' is decremented to shrink the unprocessed section.

What is the initial position of the 'high' pointer?

A At the end of the array

B At the middle of the array

C At the first occurrence of the second value

D At the start of the array

'High' starts at the last index of the array and moves backward as elements are placed in the third section.

Which of the following best describes the Dutch National Flag algorithm's space complexity?

A O(n)

B O(log n)

C O(1)

D O(n^2)

The algorithm sorts the array in-place using constant extra space.

What is the stopping condition for the Dutch National Flag algorithm?

A When mid > high

B When low > high

C When mid == low

D When all elements are equal

The algorithm stops when the 'mid' pointer passes the 'high' pointer, meaning all elements are processed.

Explain the step-by-step process of the Dutch National Flag algorithm.

Think about how the array is divided into three parts and how pointers move.

Describe why the Dutch National Flag algorithm is efficient for three-way partitioning compared to sorting.

Consider how many times each element is touched and the space used.

Practice

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

easy

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

B. To sort an array in ascending order using quicksort

C. To find the maximum element in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the partitioning goal

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

2. Step 2: Recognize the rearrangement purpose

   This helps in sorting or grouping elements efficiently without full sorting.

3. Final Answer:

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

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

Hint: Remember: three groups - 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 declare the pointers used in the Dutch National Flag algorithm in C++?

easy

A. int low = n - 1, mid = 0, high = 0;

B. int low, mid, high = 0;

C. int low = 0, mid = 0, high = n - 1;

D. int low = 0, mid = n - 1, high = 0;

Solution

1. Step 1: Identify pointer initialization

   In the algorithm, low and mid start at 0, high starts at n-1 (last index).

2. Step 2: Match correct initialization

   int low = 0, mid = 0, high = n - 1; correctly initializes low and mid to 0, high to n-1.

3. Final Answer:

   int low = 0, mid = 0, high = n - 1; -> Option C

4. Quick Check:

   Pointers start: low=0, mid=0, high=n-1 [OK]

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

Common Mistakes:

• Initializing pointers incorrectly
• Setting high to 0 instead of n-1
• Not initializing mid at 0

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. [2, 2, 1, 1, 0, 0]

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

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

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

Solution

1. Step 1: Partition array by pivot 1

   Elements less than 1: 0,0; equal to 1: 1,1; greater than 1: 2,2.

2. Step 2: Rearrange array accordingly

   Place all 0s first, then 1s, then 2s resulting in [0, 0, 1, 1, 2, 2].

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option B

4. Quick Check:

   Less, equal, greater order = [0,0,1,1,2,2] [OK]

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

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Assuming full sort instead of partition

4. Given the following code snippet for Dutch National Flag partition, what is the error?

int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
  if (arr[mid] < pivot) {
    swap(arr[low], arr[mid]);
    low++;
  } else if (arr[mid] == pivot) {
    mid++;
  } else {
    swap(arr[mid], arr[high]);
    high--;
  }
}

medium

A. Pivot value is not defined

B. Incorrect swap function usage

C. Loop condition should be mid < high

D. Missing increment of mid when arr[mid] < pivot

Solution

1. Step 1: Analyze pointer increments

   When arr[mid] < pivot, low is incremented but mid is not incremented, causing infinite loop.

2. Step 2: Identify missing mid increment

   Mid must also increment after swapping to move forward.

3. Final Answer:

   Missing increment of mid when arr[mid] < pivot -> Option D

4. Quick Check:

   Increment mid after swap for less than pivot [OK]

Hint: Always increment mid except when swapping with high [OK]

Common Mistakes:

• Forgetting to increment mid after swap with low
• Changing loop condition incorrectly
• Ignoring pivot initialization

5. You have an array arr = [3, 5, 2, 3, 8, 3, 1] and want to partition it using the Dutch National Flag algorithm with pivot = 3. Which of the following is the correct final partitioned array?

hard

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

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

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

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

Solution

1. Step 1: Group elements by pivot 3

   Less than 3: 1, 2; equal to 3: 3, 3, 3; greater than 3: 5, 8.

2. Step 2: Arrange groups in order

   Place less first, then equal, then greater: [1, 2, 3, 3, 3, 5, 8].

3. Step 3: Check options for exact order

   [1, 2, 3, 3, 3, 5, 8] matches the correct partition with greater elements 5 and 8 in any order, which is valid partitioning.

4. Final Answer:

   [1, 2, 3, 3, 3, 5, 8] -> Option A

5. Quick Check:

   Partition order less, equal, greater = [1,2,3,3,3,5,8] [OK]

Hint: Partition keeps groups, order inside groups can vary [OK]

Common Mistakes:

• Assuming full sort instead of partition
• Mixing order of greater elements
• Placing equal elements incorrectly