Sort Colors Two Pointer Dutch Flag in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dutch Flag Algorithm with Mixed Colors

What is the output of the following Rust code that sorts colors represented by 0, 1, and 2 using the Dutch Flag algorithm?

DSA Rust

fn sort_colors(nums: &mut Vec<i32>) {
    let (mut low, mut mid, mut high) = (0, 0, nums.len() - 1);
    while mid <= high {
        match nums[mid] {
            0 => {
                nums.swap(low, mid);
                low += 1;
                mid += 1;
            }
            1 => {
                mid += 1;
            }
            2 => {
                nums.swap(mid, high);
                if high == 0 { break; }
                high -= 1;
            }
            _ => {}
        }
    }
}

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

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

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

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

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

💡 Hint

Remember the Dutch Flag algorithm sorts 0s, then 1s, then 2s in one pass.

The algorithm uses three pointers: low, mid, and high. It swaps 0s to the front, 2s to the end, and leaves 1s in the middle. After processing, the vector is sorted as [0, 0, 1, 1, 2, 2].

🧠 Conceptual

intermediate

Number of Passes in Dutch Flag Algorithm

How many passes over the array does the Dutch Flag algorithm make to sort colors represented by 0, 1, and 2?

A One pass

B Three passes

C Two passes

D Four passes

💡 Hint

Think about how the pointers move and how many times each element is visited.

The Dutch Flag algorithm sorts the array in a single pass by using three pointers to partition the array into three parts.

🔧 Debug

advanced

Identify the Bug in Dutch Flag Implementation

What error will occur when running this Rust code for the Dutch Flag algorithm on an empty vector?

DSA Rust

fn sort_colors(nums: &mut Vec<i32>) {
    let (mut low, mut mid, mut high) = (0, 0, nums.len() - 1);
    while mid <= high {
        match nums[mid] {
            0 => {
                nums.swap(low, mid);
                low += 1;
                mid += 1;
            }
            1 => {
                mid += 1;
            }
            2 => {
                nums.swap(mid, high);
                high -= 1;
            }
            _ => {}
        }
    }
}

fn main() {
    let mut colors = vec![];
    sort_colors(&mut colors);
    println!("{:?}", colors);
}

A No output, program runs fine

B panic at 'index out of bounds: the len is 0 but the index is 18446744073709551615'

C panic at 'attempt to subtract with overflow'

D Compilation error due to missing semicolon

💡 Hint

Check what happens when nums.len() is zero and you subtract 1.

When nums is empty, nums.len() - 1 causes unsigned integer underflow, resulting in a very large number used as index, causing panic at index out of bounds.

📝 Syntax

advanced

Correct the Syntax Error in Dutch Flag Rust Code

Which option fixes the syntax error in this Rust code snippet for the Dutch Flag algorithm?

DSA Rust

fn sort_colors(nums: &mut Vec<i32>) {
    let (mut low, mut mid, mut high) = (0, 0, nums.len() - 1)
    while mid <= high {
        match nums[mid] {
            0 => {
                nums.swap(low, mid);
                low += 1;
                mid += 1;
            }
            1 => mid += 1,
            2 => {
                nums.swap(mid, high);
                high -= 1;
            }
            _ => {}
        }
    }
}

A Add a semicolon after the tuple assignment line: let (mut low, mut mid, mut high) = (0, 0, nums.len() - 1);

B Change the tuple assignment to use square brackets instead of parentheses

C Remove the while loop braces

D Replace match with if-else statements

💡 Hint

Rust requires semicolons after statements.

The missing semicolon after the tuple assignment causes a syntax error. Adding it fixes the code.

🚀 Application

expert

Final State of Array After Dutch Flag Algorithm

Given the input array [1, 2, 0, 1, 2, 0, 1], what is the final state of the array after applying the Dutch Flag algorithm?

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

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

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

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

💡 Hint

The algorithm sorts all 0s first, then 1s, then 2s.

The Dutch Flag algorithm partitions the array so that all 0s come first, followed by all 1s, then all 2s. The sorted array is [0, 0, 1, 1, 1, 2, 2].

Practice

1. What is the main goal of the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. To sort an array containing only 0s, 1s, and 2s in a single pass

B. To sort any array of integers in ascending order

C. To find the maximum value in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the problem context

   The algorithm is designed specifically for arrays with only three distinct values: 0, 1, and 2.

2. Step 2: Identify the sorting goal

   The goal is to rearrange the array so that all 0s come first, then all 1s, and finally all 2s, in one pass without extra space.

3. Final Answer:

   To sort an array containing only 0s, 1s, and 2s in a single pass -> Option A

4. Quick Check:

   Sort Colors = Sort 0,1,2 in one pass [OK]

Hint: Remember: Dutch Flag sorts 0,1,2 in one pass [OK]

Common Mistakes:

• Thinking it sorts any integer array
• Confusing it with general sorting algorithms
• Assuming it reverses the array

2. Which of the following Rust code snippets correctly declares the pointers used in the Dutch Flag algorithm?

easy

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

B. let low = 0; let mid = 0; let high = nums.len();

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

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

Solution

1. Step 1: Identify pointer initialization

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

2. Step 2: Check mutability and bounds

   All pointers must be mutable to move during sorting, and high must be len() - 1 to avoid out-of-bounds errors.

3. Final Answer:

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

4. Quick Check:

   Correct pointer setup = let mut low = 0; let mut mid = 0; let mut high = nums.len() - 1; [OK]

Hint: Pointers start at 0 except high at last index [OK]

Common Mistakes:

• Setting high to nums.len() causing out-of-bounds
• Not using mutable variables
• Starting pointers at wrong indices

3. What will be the output of the following Rust code after applying the Dutch Flag algorithm?

let mut nums = vec![2, 0, 2, 1, 1, 0];
let mut low = 0;
let mut mid = 0;
let mut high = nums.len() - 1;

while mid <= high {
    match nums[mid] {
        0 => {
            nums.swap(low, mid);
            low += 1;
            mid += 1;
        },
        1 => {
            mid += 1;
        },
        2 => {
            nums.swap(mid, high);
            if high == 0 { break; }
            high -= 1;
        },
        _ => {}
    }
}
println!("{:?}", nums);

medium

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

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

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

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

Solution

1. Step 1: Trace initial swaps and pointer moves

   Starting with nums = [2,0,2,1,1,0], the algorithm swaps 2 at mid with 0 at high, then moves pointers accordingly.

2. Step 2: Continue until mid passes high

   After all swaps and increments, the array becomes sorted as [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Swap 0s left, 2s right, 1s stay middle [OK]

Common Mistakes:

• Not updating pointers correctly after swap
• Swapping with wrong indices
• Stopping loop too early

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

let mut nums = vec![2, 0, 1];
let mut low = 0;
let mut mid = 0;
let mut high = nums.len();

while mid <= high {
    match nums[mid] {
        0 => {
            nums.swap(low, mid);
            low += 1;
            mid += 1;
        },
        1 => {
            mid += 1;
        },
        2 => {
            nums.swap(mid, high);
            high -= 1;
        },
        _ => {}
    }
}

medium

A. The match statement is missing a case for 3

B. mid pointer is not incremented after swapping 2

C. low pointer is incremented incorrectly

D. high is initialized to nums.len(), causing out-of-bounds access

Solution

1. Step 1: Check pointer initialization

   high is set to nums.len(), which is one past the last valid index, causing out-of-bounds when accessing nums[high].

2. Step 2: Understand valid index range

   Valid indices are 0 to nums.len() - 1, so high should be initialized to nums.len() - 1.

3. Final Answer:

   high is initialized to nums.len(), causing out-of-bounds access -> Option D

4. Quick Check:

   high must be last index, not length [OK]

Hint: high = length - 1 to avoid out-of-bounds [OK]

Common Mistakes:

• Using length instead of last index for high
• Not incrementing mid after swapping 2
• Ignoring pointer bounds

5. Given an array nums = [1, 2, 0, 1, 2, 0, 1], how many swaps will the Dutch Flag algorithm perform to sort it?

hard

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Trace swaps during sorting

   Initial array: [1, 2, 0, 1, 2, 0, 1]. Swaps occur when 0 or 2 is found at mid.

2. Step 2: Count swaps step-by-step

   Swaps: - Swap 0 at index 2 with 1 at low (index 0) -> 1 swap - Swap 2 at index 1 with 1 at high (index 6) -> 1 swap - Swap 0 at index 5 with 1 at low (index 1) -> 1 swap - Swap 2 at index 1 with 1 at high (index 5) -> 1 swap Total swaps = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Count swaps for 0 and 2 moves = 4 [OK]

Hint: Count swaps only when swapping 0 or 2 [OK]

Common Mistakes:

• Counting pointer moves as swaps
• Missing swaps when 2 is swapped
• Assuming swaps equal array length