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 Array

What is the output of the following code after performing the Dutch National Flag partition on the array?

DSA C

void dutchFlagPartition(int arr[], int size, int pivot) {
    int low = 0, mid = 0, high = size - 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--;
        }
    }
}

int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int size = 6;
    int pivot = 1;
    dutchFlagPartition(arr, size, pivot);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A 1 1 0 0 2 2

B 2 2 1 1 0 0

C 0 1 0 1 2 2

D 0 0 1 1 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. The final array is sorted in that order.

🧠 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 can perform in the worst case?

A n

B 2n

C n/2

D 3n

💡 Hint

The algorithm performs one swap for each element < pivot or > pivot.

In the worst case, there are no elements equal to pivot, so each of the n elements causes one swap.

🔧 Debug

advanced

Identify the bug in Dutch National Flag implementation

What error does the following code produce when run on array {1, 2, 0} with pivot 1?

DSA C

void dutchFlagPartition(int arr[], int size, int pivot) {
    int low = 0, mid = 0, high = size - 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--;
        }
    }
}

int main() {
    int arr[] = {1, 2, 0};
    int size = 3;
    int pivot = 1;
    dutchFlagPartition(arr, size, pivot);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A Array index out of bounds

B Incorrect output

C Correct output: 0 1 2

D Segmentation fault

💡 Hint

Check the loop condition carefully and how mid and high pointers move.

The loop condition should be mid <= high. Using mid < high causes the loop to miss processing when mid == high, leading to an incorrect output.

📝 Syntax

advanced

Syntax error in Dutch National Flag code snippet

Which option contains a syntax error in the Dutch National Flag partition implementation?

DSA C

void dutchFlagPartition(int arr[], int size, int pivot) {
    int low = 0, mid = 0, high = size - 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--;
        }
    }
}

A No syntax error

B Missing closing brace for while loop

C Missing type declaration for temp variable

D Missing semicolon after high--

💡 Hint

Check all braces and semicolons carefully.

The code snippet is syntactically correct with all braces and semicolons properly placed.

🚀 Application

expert

Using Dutch National Flag for Sorting Colors

Given an array representing colors as integers 0 (red), 1 (white), and 2 (blue), which option correctly sorts the array using the Dutch National Flag algorithm?

DSA C

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            high--;
        }
    }
}

A Sorts array but only works if array is already partially sorted

B Sorts array but uses extra O(n) space for temporary array

C Sorts array in one pass with O(n) time and O(1) space

D Sorts array in O(n^2) time due to nested loops

💡 Hint

Dutch National Flag algorithm is known for linear time and constant space sorting of three distinct values.

The algorithm sorts the array in one pass using three pointers, achieving O(n) time and O(1) space complexity.

Practice

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

easy

A. To sort an array in ascending order using quicksort

B. To rearrange an array into three parts: less than, equal to, and greater than a pivot

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 based on a pivot value: elements less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Compare with other options

   Options A, C, and D describe different operations: sorting, finding max, and reversing, which are not the main goal here.

3. Final Answer:

   To rearrange an array into three parts: less than, equal to, and greater than a pivot -> Option B

4. Quick Check:

   Partitioning = three parts [OK]

Hint: Remember: three parts based on pivot value [OK]

Common Mistakes:

• Confusing with full sorting algorithms
• Thinking it only separates two parts
• Assuming it finds max or min values

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 = 0, mid = 0, high = n - 1;

B. int low, mid, high = 0;

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

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

Solution

1. Step 1: Understand pointer initialization

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

2. Step 2: Check each option

   int low = 0, mid = 0, high = n - 1; correctly initializes low and mid to 0, high to n-1. Others have incorrect initial values.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Setting low or mid to n or n-1 incorrectly
• Not initializing all pointers
• Confusing variable assignments

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

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

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

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

Solution

1. Step 1: Partition array around 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 A

4. Quick Check:

   Partitioned array = [0,0,1,1,2,2] [OK]

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

Common Mistakes:

• Mixing order of groups
• Not grouping equal elements correctly
• Assuming full sorting instead of partitioning

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

void dnfPartition(int arr[], int n, int pivot) {
  int low = 0, mid = 0, high = n - 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. Pivot comparison should use > instead of <

B. The loop condition should be mid < high

C. Pointers low and mid should start at n-1

D. swap function is not defined for array elements

Solution

1. Step 1: Check swap usage

   The code uses swap(arr[low], arr[mid]) but swap is not a built-in function in C for array elements.

2. Step 2: Verify other parts

   Loop condition and pointer initialization are correct. Pivot comparisons are correct as per algorithm.

3. Final Answer:

   swap function is not defined for array elements -> Option D

4. Quick Check:

   Missing swap definition = error [OK]

Hint: Remember to define or implement swap for array elements [OK]

Common Mistakes:

• Assuming swap is built-in for arrays in C
• Changing loop condition incorrectly
• Wrong pointer initialization

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

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Trace swaps during partition

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

2. Step 2: Count total swaps

   Total swaps performed = 4

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count swaps carefully = 4 [OK]

Hint: Count swaps during each pointer move carefully [OK]

Common Mistakes:

• Counting swaps only when mid moves
• Ignoring swaps after swapping with high
• Miscounting swaps when elements equal pivot