Dutch National Flag Three Way Partition in DSA Java

Mental Model

We rearrange an array so that all elements less than a pivot come first, then elements equal to the pivot, then elements greater than the pivot.

Analogy: Imagine sorting colored balls into three bins: red balls go to the first bin, white balls to the second, and blue balls to the third, all in one pass without extra space.

array: [ 2, 0, 2, 1, 1, 0 ]
indexes:  0  1  2  3  4  5
pointers: low ↑    mid ↑           high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0], pivot = 1

Goal: Rearrange array so that all 0s come first, then all 1s, then all 2s

Step 1: mid=0, value=2 > pivot, swap with high=5 (value=0), decrement high

[0, 0, 2, 1, 1, 2]
low=0, mid=0, high=4

Why: Move larger elements to the end to separate them

Step 2: mid=0, value=0 < pivot, swap with low=0, increment low and mid

[0, 0, 2, 1, 1, 2]
low=1, mid=1, high=4

Why: Move smaller elements to the front

Step 3: mid=1, value=0 < pivot, swap with low=1, increment low and mid

[0, 0, 2, 1, 1, 2]
low=2, mid=2, high=4

Why: Continue moving smaller elements to the front

Step 4: mid=2, value=2 > pivot, swap with high=4 (value=1), decrement high

[0, 0, 1, 1, 2, 2]
low=2, mid=2, high=3

Why: Move larger elements to the end

Step 5: mid=2, value=1 == pivot, increment mid

[0, 0, 1, 1, 2, 2]
low=2, mid=3, high=3

Why: Keep equal elements in the middle

Step 6: mid=3, value=1 == pivot, increment mid

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

Why: All elements processed, done

Result:

Final array: [0, 0, 1, 1, 2, 2]

Annotated Code

DSA Java

public class DutchNationalFlag {
    public static void threeWayPartition(int[] arr, int pivot) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] < pivot) {
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;
                low++;
                mid++;
            } else if (arr[mid] == pivot) {
                mid++;
            } else { // arr[mid] > pivot
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        int pivot = 1;
        threeWayPartition(arr, pivot);
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

while (mid <= high) {

loop until mid passes high to process all elements

if (arr[mid] < pivot) {

if current element is smaller than pivot, swap to front

low++; mid++;

advance low and mid pointers after placing smaller element

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

if equal to pivot, just move mid forward

mid++;

advance mid pointer to keep equal elements in middle

else { // arr[mid] > pivot

if greater than pivot, swap with high and decrement high

high--;

decrement high pointer after moving larger element to end

Output

0 0 1 1 2 2 

Complexity Analysis

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

Space: O(1) because swaps happen in place without extra storage

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

Edge Cases

empty array

function completes immediately without changes

DSA Java

while (mid <= high) {

all elements equal to pivot

mid pointer moves through all elements without swaps

DSA Java

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

no elements less than pivot

low pointer stays at 0, swaps only move larger elements to end

DSA Java

if (arr[mid] < pivot) {

When to Use This Pattern

When you need to separate an array into three groups 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

Summary

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

Use when you want to partition data quickly without full sorting.

The key is to use three pointers and swap elements in one pass without extra space.

Practice

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

easy

A. To reverse the elements of an array

B. To rearrange an array into three parts based on a pivot value

C. To find the maximum element in an array

D. To sort an array in ascending order

Solution

1. Step 1: Understand the algorithm's purpose

   The Dutch National Flag algorithm divides an array into three parts: elements less than, equal to, and greater than a pivot.

2. Step 2: Compare with other options

   Sorting or finding max are different tasks; reversing is unrelated.

3. Final Answer:

   To rearrange an array into three parts based on a pivot value -> Option B

4. Quick Check:

   Partitioning by pivot = D [OK]

Hint: Remember: It partitions into three groups around a pivot [OK]

Common Mistakes:

• Confusing partitioning with sorting
• Thinking it finds max or min values
• Assuming it reverses the array

2. Which of the following is the correct Java syntax to swap two elements arr[i] and arr[j] in an integer array?

easy

A. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i] = arr[j]; arr[j] = arr[i];

C. swap(arr[i], arr[j]);

D. int temp = arr[i]; arr[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Understand swapping logic

   Swapping requires a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   swap(arr[i], arr[j]); assumes a non-existent swap function; arr[i] = arr[j]; arr[j] = arr[i]; overwrites arr[i] without saving; int temp = arr[i]; arr[i] = arr[j]; arr[j] = arr[i]; loses original arr[i] value by assigning arr[j] = arr[i] after changing arr[i]; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; correctly uses temp.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Use temp variable for swap = C [OK]

Hint: Use a temp variable to swap two array elements safely [OK]

Common Mistakes:

• Overwriting one element before saving it
• Using a non-existent swap function
• Swapping without a temporary variable

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

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

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

D. [0, 0, 1, 1, 2, 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: Arrange in order less, equal, greater

   So the array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

   Partitioned array = A [OK]

Hint: Group elements less, equal, then greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Ignoring pivot value placement

4. Identify the error in this Java code snippet for Dutch National Flag partition:

int low = 0, mid = 0, high = arr.length - 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--;
  }
}

medium

A. The pivot comparison should use > instead of <

B. The loop condition should be mid < high

C. swap function is called incorrectly with array elements instead of indices

D. The variables low, mid, high are not initialized properly

Solution

1. Step 1: Check swap function usage

   swap(arr[low], arr[mid]) passes values, not indices; swap needs indices to swap elements in array.

2. Step 2: Verify other parts

   Loop condition and variable initialization are correct; pivot comparisons are standard.

3. Final Answer:

   swap function is called incorrectly with array elements instead of indices -> Option C

4. Quick Check:

   Swap needs indices, not values = A [OK]

Hint: Swap array elements by indices, not by passing values [OK]

Common Mistakes:

• Passing values instead of indices to swap
• Wrong loop boundary condition
• Incorrect pivot comparison operators

5. Given an array arr = [3, 5, 2, 1, 4, 3, 2] and pivot = 3, how many swaps will the Dutch National Flag algorithm perform to partition the array?

hard

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Trace swaps during partition

   Initial: low=0, mid=0, high=6 - mid=0 (3 == pivot): mid++ (0 swaps) - mid=1 (5 > pivot): swap arr[mid] and arr[high] -> swap arr[1] and arr[6] (swap 1), high--=5 - mid=1 (now 2 < pivot): swap arr[low] and arr[mid] -> swap arr[0] and arr[1] (swap 2), low++=1, mid++=2 - mid=2 (2 < pivot): swap arr[low] and arr[mid] -> swap arr[1] and arr[2] (swap 3), low++=2, mid++=3 - mid=3 (1 < pivot): swap arr[low] and arr[mid] -> swap arr[2] and arr[3] (swap 4), low++=3, mid++=4 - mid=4 (4 > pivot): swap arr[mid] and arr[high] -> swap arr[4] and arr[5] (swap 5), high--=4 - mid=4 (now 3 == pivot): mid++=5 Loop ends as mid > high.

2. Step 2: Count total swaps

   Total swaps counted = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Count swaps carefully during partition = B [OK]

Hint: Count swaps when elements move across low, mid, high pointers [OK]

Common Mistakes:

• Counting swaps incorrectly when pivot equals element
• Ignoring swaps after high pointer moves
• Assuming one swap per iteration