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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch National Flag Partition on a sample array

What is the output of the following Rust code that partitions an array using the Dutch National Flag algorithm with pivot = 2?

DSA Rust

fn dutch_national_flag(arr: &mut [i32], pivot: i32) {
    let mut low = 0;
    let mut mid = 0;
    let mut high = arr.len() - 1;

    while mid <= high {
        if arr[mid] < pivot {
            arr.swap(low, mid);
            low += 1;
            mid += 1;
        } else if arr[mid] == pivot {
            mid += 1;
        } else {
            arr.swap(mid, high);
            if high == 0 { break; } // prevent underflow
            high -= 1;
        }
    }
}

fn main() {
    let mut arr = [3, 2, 1, 2, 3, 1, 2];
    dutch_national_flag(&mut arr, 2);
    println!("{:?}", arr);
}

A [3, 3, 2, 2, 2, 1, 1]

B [1, 2, 1, 2, 2, 3, 3]

C [1, 1, 2, 2, 2, 3, 3]

D [1, 1, 3, 3, 2, 2, 2]

💡 Hint

Remember the algorithm groups elements less than pivot first, then equal, then greater.

The Dutch National Flag algorithm rearranges the array so that all elements less than the pivot come first, followed by elements equal to the pivot, then elements greater than the pivot. Here, 1 < 2, so 1s come first, then all 2s, then 3s.

🧠 Conceptual

intermediate

Understanding pointers in Dutch National Flag algorithm

In the Dutch National Flag algorithm, what is the role of the 'mid' pointer during the partitioning process?

A It scans through the array to classify elements as less than, equal to, or greater than the pivot.

B It is used to swap elements greater than the pivot to the front.

C It points to the last element greater than the pivot.

D It marks the boundary between elements less than and equal to the pivot.

💡 Hint

Think about which pointer moves through the array to check each element.

The 'mid' pointer moves through the array from start to end, examining each element to decide if it should be swapped to the less than, equal to, or greater than section.

🔧 Debug

advanced

Identify the error in this Dutch National Flag implementation

What error will this Rust code produce when run, and why?

DSA Rust

fn dutch_national_flag(arr: &mut [i32], pivot: i32) {
    let mut low = 0;
    let mut mid = 0;
    let mut high = arr.len() - 1;

    while mid <= high {
        if arr[mid] < pivot {
            arr.swap(low, mid);
            low += 1;
            mid += 1;
        } else if arr[mid] == pivot {
            mid += 1;
        } else {
            arr.swap(mid, high);
            high -= 1;
        }
    }
}

fn main() {
    let mut arr = [2, 0, 1];
    dutch_national_flag(&mut arr, 1);
    println!("{:?}", arr);
}

A Infinite loop because 'mid' is never incremented

B Index out of bounds panic because 'high' is initialized to arr.len() instead of arr.len() - 1

C Compilation error due to missing semicolon

D No error, outputs [0, 1, 2]

💡 Hint

Check the initial value of 'high' and how it is used as an index.

Array indices go from 0 to arr.len() - 1. Initializing 'high' to arr.len() causes an out-of-bounds access when swapping.

❓ Predict Output

advanced

Result of Dutch National Flag partition with all elements equal to pivot

What is the output of this Rust code when all elements are equal to the pivot?

DSA Rust

fn dutch_national_flag(arr: &mut [i32], pivot: i32) {
    let mut low = 0;
    let mut mid = 0;
    let mut high = arr.len() - 1;

    while mid <= high {
        if arr[mid] < pivot {
            arr.swap(low, mid);
            low += 1;
            mid += 1;
        } else if arr[mid] == pivot {
            mid += 1;
        } else {
            arr.swap(mid, high);
            high -= 1;
        }
    }
}

fn main() {
    let mut arr = [5, 5, 5, 5];
    dutch_national_flag(&mut arr, 5);
    println!("{:?}", arr);
}

A []

B [5, 5, 5, 5, 5]

C [5, 5, 5]

D [5, 5, 5, 5]

💡 Hint

If all elements equal pivot, the array remains unchanged.

Since all elements equal the pivot, the algorithm only increments 'mid' without swapping, so the array stays the same.

🚀 Application

expert

Number of swaps in Dutch National Flag partition

Given the array [3, 1, 2, 2, 1, 3, 2] and pivot = 2, how many swaps does the Dutch National Flag algorithm perform to partition the array?

A 4

B 5

C 3

D 6

💡 Hint

Trace the algorithm step-by-step counting swaps.

Swaps occur when elements less than or greater than pivot are moved. Counting carefully yields 4 swaps.

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

B. To reverse the elements of an array

C. To find the maximum element in an array

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

Solution

1. Step 1: Understand the problem goal

   The algorithm divides the array into three parts: less than pivot, equal to pivot, and greater than 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 D

4. Quick Check:

   Partitioning by pivot = rearrange into three parts [OK]

Hint: Remember: Dutch Flag splits array into three color groups [OK]

Common Mistakes:

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

2. Which of the following Rust code snippets correctly declares mutable indices for the Dutch National Flag algorithm?

easy

A. let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1;

B. let low = 0; let mid = 0; let high = arr.len() - 1;

C. let mut low = 0; let mid = 0; let mut high = arr.len() - 1;

D. let low = 0; let mut mid = 0; let high = arr.len() - 1;

Solution

1. Step 1: Identify mutability requirement

   Indices must be mutable to update during partitioning.

2. Step 2: Check each declaration

   Only let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1; declares all three indices as mutable.

3. Final Answer:

   let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1; -> Option A

4. Quick Check:

   All indices mutable = correct declaration [OK]

Hint: Indices change, so declare all as mutable with 'mut' [OK]

Common Mistakes:

• Forgetting 'mut' keyword for variables that change
• Mixing mutable and immutable declarations incorrectly
• Using immutable variables causing compile errors

3. What will be the output of the following Rust code after applying the Dutch National Flag partition with pivot = 1?

let mut arr = vec![2, 0, 2, 1, 1, 0];
let pivot = 1;
// After partitioning
// arr = ?

medium

A. [1, 1, 0, 0, 2, 2]

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

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

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

Solution

1. Step 1: Understand partitioning by pivot 1

   Elements less than 1 go first (0s), then equal to 1, then greater than 1 (2s).

2. Step 2: Rearrange array accordingly

   Original: [2, 0, 2, 1, 1, 0] After partition: [0, 0, 1, 1, 2, 2]

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of less and greater groups
• Assuming full sorting instead of partitioning

4. Identify the bug in this Rust code snippet implementing Dutch National Flag partition:

let mut low = 0;
let mut mid = 0;
let mut high = arr.len() - 1;
while mid <= high {
    if arr[mid] < pivot {
        arr.swap(low, mid);
        low += 1;
        mid += 1;
    } else if arr[mid] == pivot {
        mid += 1;
    } else {
        arr.swap(mid, high);
        high -= 1;
    }
}

medium

A. mid should be decremented in else block

B. Incorrect comparison operators for pivot

C. Missing increment of mid after swapping with low

D. high should be incremented instead of decremented

Solution

1. Step 1: Analyze pointer updates after swaps

   When swapping arr[low] and arr[mid], mid must also move forward to avoid infinite loop.

2. Step 2: Identify missing mid increment

   Code increments mid only when arr[mid] == pivot, but not after swapping with low.

3. Final Answer:

   Missing increment of mid after swapping with low -> Option C

4. Quick Check:

   mid must increment after swap with low to progress [OK]

Hint: Increment mid after swapping with low to avoid infinite loop [OK]

Common Mistakes:

• Forgetting to increment mid after swap with low
• Changing mid incorrectly in else block
• Misunderstanding pointer movements

5. Given an array with elements 0, 1, and 2 representing colors red, white, and blue respectively, how would you modify the Dutch National Flag algorithm to sort the array so that all reds come first, whites second, and blues last? Choose the correct approach.

hard

A. Use three pointers low, mid, high; move mid forward, swap with low if 0, swap with high if 2.

B. Sort the array using Rust's built-in sort() method.

C. Use two pointers only, swapping elements when needed.

D. Count the number of 0s, 1s, and 2s, then overwrite the array accordingly.

Solution

1. Step 1: Understand the Dutch National Flag approach

   It uses three pointers to partition the array into three parts efficiently in one pass.

2. Step 2: Compare with other methods

   Built-in sort or counting are valid but not the Dutch National Flag algorithm; two pointers are insufficient for three groups.

3. Final Answer:

   Use three pointers low, mid, high; move mid forward, swap with low if 0, swap with high if 2. -> Option A

4. Quick Check:

   Three pointers and swaps = Dutch National Flag method [OK]

Hint: Three pointers: low, mid, high handle 0,1,2 in one pass [OK]

Common Mistakes:

• Using sorting instead of partitioning
• Trying two pointers for three groups
• Ignoring efficient one-pass solution