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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on an array

What is the output of the following C++ code that partitions the array using the Dutch National Flag algorithm with pivot = 1?

DSA C++

void dutchFlagPartition(int pivot, std::vector<int>& arr) {
    int smaller = 0, equal = 0, larger = arr.size() - 1;
    while (equal <= larger) {
        if (arr[equal] < pivot) {
            std::swap(arr[smaller++], arr[equal++]);
        } else if (arr[equal] == pivot) {
            equal++;
        } else {
            std::swap(arr[equal], arr[larger--]);
        }
    }
}

int main() {
    std::vector<int> arr = {2, 0, 2, 1, 1, 0};
    dutchFlagPartition(1, arr);
    for (int x : arr) std::cout << x << " ";
    return 0;
}

A 0 1 1 0 2 2

B 2 2 1 1 0 0

C 0 0 1 1 2 2

D 1 1 0 0 2 2

💡 Hint

Remember the algorithm moves elements less than pivot to the front, equal in the middle, and greater to the end.

The Dutch National Flag algorithm partitions the array into three parts: less than pivot, equal to pivot, and greater than pivot. After running, all 0s (less than 1) come first, then all 1s, then all 2s.

🧠 Conceptual

intermediate

Understanding the pointers in Dutch National Flag algorithm

In the Dutch National Flag algorithm, what is the role of the 'equal' pointer during the partitioning process?

A It scans through the array to classify elements as less than, equal to, or greater than the pivot.

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

C It points to the last element greater than the pivot.

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

💡 Hint

Think about which pointer moves through the array checking each element.

The 'equal' pointer scans the array from left to right, classifying each element and swapping as needed to partition the array.

🔧 Debug

advanced

Identify the bug in this Dutch National Flag implementation

What error will this C++ code produce when run, and why?

DSA C++

void dutchFlagPartition(int pivot, std::vector<int>& arr) {
    int smaller = 0, equal = 0, larger = arr.size();
    while (equal < larger) {
        if (arr[equal] < pivot) {
            std::swap(arr[smaller++], arr[equal++]);
        } else if (arr[equal] == pivot) {
            equal++;
        } else {
            std::swap(arr[equal], arr[larger--]);
        }
    }
}

A No error, code runs correctly

B Infinite loop because 'equal' never increments

C Compilation error due to missing return type

D Runtime error due to out-of-range access on 'arr[larger--]'

💡 Hint

Check the initial value of 'larger' and how it is used as an index.

The 'larger' pointer is initialized to arr.size(), which is out of bounds for zero-based indexing. Accessing arr[larger] causes runtime error.

🚀 Application

advanced

Applying Dutch National Flag to sort colors

Given an array representing colors as integers 0 (red), 1 (white), and 2 (blue), which option shows the array after applying Dutch National Flag partition with pivot = 1?

DSA C++

std::vector<int> colors = {2, 0, 1, 2, 1, 0};
dutchFlagPartition(1, colors);
// Output the array

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

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

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

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

💡 Hint

The algorithm groups all 0s first, then 1s, then 2s.

The Dutch National Flag algorithm sorts the array so that all 0s come first, then 1s, then 2s.

❓ Predict Output

expert

Final state of pointers after partitioning

After running the Dutch National Flag partition on array {1, 2, 0, 1, 2, 0} with pivot = 1, what are the final values of pointers 'smaller', 'equal', and 'larger'?

DSA C++

void dutchFlagPartition(int pivot, std::vector<int>& arr, int& smaller, int& equal, int& larger) {
    smaller = 0; equal = 0; larger = arr.size() - 1;
    while (equal <= larger) {
        if (arr[equal] < pivot) {
            std::swap(arr[smaller++], arr[equal++]);
        } else if (arr[equal] == pivot) {
            equal++;
        } else {
            std::swap(arr[equal], arr[larger--]);
        }
    }
}

int main() {
    std::vector<int> arr = {1, 2, 0, 1, 2, 0};
    int smaller, equal, larger;
    dutchFlagPartition(1, arr, smaller, equal, larger);
    std::cout << smaller << " " << equal << " " << larger;
    return 0;
}

A 2 5 2

B 3 4 2

C 2 4 3

D 3 5 1

💡 Hint

Trace the pointers as elements are swapped and moved.

After partitioning, 'smaller' and 'equal' point just past the last element less than or equal to pivot, 'larger' points to the last element greater than pivot.

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