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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on Mixed Array

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

DSA Java

public class DNFFunction {
    public static void dutchNationalFlag(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 {
                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};
        dutchNationalFlag(arr, 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

A 1 1 0 0 2 2

B 0 1 0 1 2 2

C 2 2 1 1 0 0

D 0 0 1 1 2 2

💡 Hint

Focus on how the pointers low, mid, and high move and swap elements based on comparison with pivot.

The algorithm partitions the array into three parts: less than pivot (0), equal to pivot (1), and greater than pivot (2). After processing, the array is sorted as 0 0 1 1 2 2.

🧠 Conceptual

intermediate

Number of swaps in Dutch National Flag Algorithm

Given an array of size n with only three distinct values, what is the maximum number of swaps the Dutch National Flag algorithm performs in the worst case?

A n log n

B n

C n/2

D 2n

💡 Hint

Each element is swapped at most once or twice during partitioning.

In the worst case, each element can be swapped at most once, so the maximum number of swaps is proportional to n.

🔧 Debug

advanced

Identify the bug in this Dutch National Flag implementation

What error will this Java code produce when run?

DSA Java

public class DNFBug {
    public static void dnf(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 {
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

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

A No output, program terminates normally

B ArrayIndexOutOfBoundsException

C Infinite loop

D Syntax error

💡 Hint

Check the loop condition and how pointers move inside the loop.

The loop condition 'mid < high' causes the loop to miss processing when mid equals high, leading to an infinite loop in some cases.

📝 Syntax

advanced

Correct syntax for swapping elements in Java array

Which option correctly swaps elements arr[i] and arr[j] in Java?

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[j]; arr[j] = arr[i]; arr[i] = temp;

💡 Hint

Java does not support tuple unpacking or direct swap function for primitives.

Option A uses a temporary variable to swap values correctly. Option A swaps but assigns incorrectly, causing wrong swap.

🚀 Application

expert

Resulting array after multiple Dutch National Flag partitions

Given the array [3, 2, 1, 2, 3, 1, 2] and applying the Dutch National Flag partition twice: first with pivot=2, then with pivot=3, what is the final array?

DSA Java

public class DNFDualPartition {
    public static void dnf(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 {
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

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

A 1 1 2 2 2 3 3

B 1 1 2 2 3 3 2

C 1 2 1 2 2 3 3

D 3 3 2 2 2 1 1

💡 Hint

Apply the partition step by step and track the array after each partition.

First partition with pivot=2 sorts elements into <2, ==2, >2. Then partition with pivot=3 sorts the array further, resulting in sorted order 1 1 2 2 2 3 3.

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