Dutch National Flag Three Way Partition in DSA Rust - Build from Scratch

Dutch National Flag Three Way Partition

📖 Scenario: Imagine you have a box of colored balls represented by numbers: 0 for red, 1 for white, and 2 for blue. You want to sort them so that all reds come first, then whites, then blues, just like the Dutch flag.

🎯 Goal: You will write a Rust program that rearranges a list of numbers containing 0s, 1s, and 2s so that all 0s come first, then all 1s, and then all 2s. This is called the Dutch National Flag problem.

📋 What You'll Learn

Create a vector called colors with the exact values [2, 0, 2, 1, 1, 0]

Create a variable called pivot and set it to 1

Implement the Dutch National Flag partition algorithm using three pointers: low, mid, and high

Print the colors vector after partitioning

💡 Why This Matters

🌍 Real World

Sorting items into three categories quickly is useful in many real-world tasks like sorting colored balls, organizing tasks by priority, or grouping data.

💼 Career

Understanding this algorithm helps in interviews and coding tests, and teaches efficient in-place sorting techniques used in software development.

1

Create the initial colors vector

Create a vector called colors with the exact values [2, 0, 2, 1, 1, 0].

DSA Rust

# Create the colors vector with the given values
# Your code here

Hint

Use let mut colors = vec![2, 0, 2, 1, 1, 0]; to create a mutable vector.

2

Set the pivot value

Create a variable called pivot and set it to 1.

DSA Rust

fn main() {
    let mut colors = vec![2, 0, 2, 1, 1, 0];
    // Set the pivot value
    // Your code here
}

Hint

Use let pivot = 1; to set the pivot value.

3

Implement the Dutch National Flag partition algorithm

Implement the Dutch National Flag partition algorithm using three variables: low, mid, and high. Use a while loop with the condition mid <= high to rearrange the colors vector in place.

DSA Rust

fn main() {
    let mut colors = vec![2, 0, 2, 1, 1, 0];
    let pivot = 1;
    // Implement the partition algorithm here
    // Your code here
}

Hint

Use three pointers low, mid, and high. Swap elements to reorder the vector.

4

Print the partitioned colors vector

Print the colors vector after partitioning using println!("{:?}", colors);.

DSA Rust

fn main() {
    let mut colors = vec![2, 0, 2, 1, 1, 0];
    let pivot = 1;
    let mut low = 0;
    let mut mid = 0;
    let mut high = colors.len() - 1;

    while mid <= high {
        if colors[mid] < pivot {
            colors.swap(low, mid);
            low += 1;
            mid += 1;
        } else if colors[mid] == pivot {
            mid += 1;
        } else {
            colors.swap(mid, high);
            if high == 0 { break; } // prevent underflow
            high -= 1;
        }
    }
    // Print the colors vector
    // Your code here
}

Hint

Use println!("{:?}", colors); to print the vector.

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