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.