Dutch National Flag Three Way Partition in DSA C++

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, by moving balls only once through the line.

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 0s come first, then all 1s, then all 2s

Step 1: mid points to 2 (index 0), which is greater than pivot; swap with high (index 6)

Array: [2, 0, 2, 1, 1, 0, 2]
Pointers: low=0, mid=0, high=6
After swap: [2, 0, 2, 1, 1, 0, 2]
(high moves left to 5)

Why: We move the larger element to the end to group all greater elements at the right

Step 2: mid points to 2 (index 0), still greater than pivot; swap with high (index 5)

Array: [2, 0, 2, 1, 1, 0, 2]
Pointers: low=0, mid=0, high=5
After swap: [0, 0, 2, 1, 1, 2, 2]
(high moves left to 4)

Why: Continue moving large elements to the right side

Step 3: mid points to 0 (index 0), less than pivot; swap with low (index 0)

Array: [0, 0, 2, 1, 1, 2, 2]
Pointers: low=0, mid=0, high=4
After swap: [0, 0, 2, 1, 1, 2, 2]
(low and mid move right to 1)

Why: Place smaller elements at the front

Step 4: mid points to 0 (index 1), less than pivot; swap with low (index 1)

Array: [0, 0, 2, 1, 1, 2, 2]
Pointers: low=1, mid=1, high=4
After swap: [0, 0, 2, 1, 1, 2, 2]
(low and mid move right to 2)

Why: Continue grouping smaller elements at the front

Step 5: mid points to 2 (index 2), greater than pivot; swap with high (index 4)

Array: [0, 0, 2, 1, 1, 2, 2]
Pointers: low=2, mid=2, high=4
After swap: [0, 0, 1, 1, 2, 2, 2]
(high moves left to 3)

Why: Move larger elements to the right side

Step 6: mid points to 1 (index 2), equal to pivot; move mid right

Array: [0, 0, 1, 1, 2, 2, 2]
Pointers: low=2, mid=3, high=3

Why: Keep equal elements in the middle

Step 7: mid points to 1 (index 3), equal to pivot; move mid right

Array: [0, 0, 1, 1, 2, 2, 2]
Pointers: low=2, mid=4, high=3

Why: All elements processed as mid crossed high

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void dutchNationalFlagPartition(vector<int>& arr, int pivot) {
    int low = 0, mid = 0, high = (int)arr.size() - 1;
    while (mid <= high) {
        if (arr[mid] < pivot) {
            swap(arr[low], arr[mid]);
            low++;
            mid++;
        } else if (arr[mid] == pivot) {
            mid++;
        } else {
            swap(arr[mid], arr[high]);
            high--;
        }
    }
}

int main() {
    vector<int> arr = {2, 0, 2, 1, 1, 0, 2};
    int pivot = 1;
    dutchNationalFlagPartition(arr, pivot);
    for (int num : arr) {
        cout << num << " -> ";
    }
    cout << "null" << endl;
    return 0;
}

while (mid <= high) {

continue processing elements until mid passes high

if (arr[mid] < pivot) {

current element is smaller than pivot, swap to front

swap(arr[low], arr[mid]);

move smaller element to low partition

low++; mid++;

expand smaller and middle partitions

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

element equals pivot, just move mid forward

mid++;

expand middle partition

else {

element greater than pivot, swap to end

swap(arr[mid], arr[high]);

move larger element to high partition

high--;

reduce high partition boundary

Output

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

Complexity Analysis

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

Space: O(1) because rearrangement is done in place without extra storage

vs Alternative: Compared to sorting the entire array O(n log n), this is faster and more efficient for three-way partitioning

Edge Cases

empty array

function completes immediately without changes

DSA C++

while (mid <= high) {

all elements equal to pivot

mid moves through all elements without swaps

DSA C++

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

no elements less than pivot

all smaller swaps skipped, larger elements moved to end

DSA C++

if (arr[mid] < pivot) {

When to Use This Pattern

When you need to sort or group an array into three categories 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 or missed elements
Fix: Always swap with low or high pointers correctly and update pointers accordingly

Summary

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

Use when you want to group elements around a pivot efficiently in one pass.

The key is to use three pointers to track boundaries and swap elements accordingly without extra space.

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