Dutch National Flag Three Way Partition in DSA Rust

Mental Model

We rearrange an array into three parts: smaller than pivot, equal to pivot, and greater than pivot, all in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick each ball once and put it in the right bin without extra space.

array: [ 2, 0, 2, 1, 1, 0 ]
indexes:  ↑   ↑        
          low curr     high
Three zones:
[ < pivot | == pivot | > pivot ]

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0], pivot = 1

Goal: Rearrange array so all 0s come first, then 1s, then 2s

Step 1: curr at index 0, value 2 > pivot, swap with high index 5 value 0, decrease high

[0, 0, 2, 1, 1, 2]
low=0 curr=0 high=4

Why: Move large value to the end to separate > pivot zone

Step 2: curr at index 0, value 0 < pivot, swap with low index 0, increase low and curr

[0, 0, 2, 1, 1, 2]
low=1 curr=1 high=4

Why: Move small value to the front to separate < pivot zone

Step 3: curr at index 1, value 0 < pivot, swap with low index 1, increase low and curr

[0, 0, 2, 1, 1, 2]
low=2 curr=2 high=4

Why: Continue moving small values to front

Step 4: curr at index 2, value 2 > pivot, swap with high index 4 value 1, decrease high

[0, 0, 1, 1, 2, 2]
low=2 curr=2 high=3

Why: Move large value to end

Step 5: curr at index 2, value 1 == pivot, just increase curr

[0, 0, 1, 1, 2, 2]
low=2 curr=3 high=3

Why: Keep equal values in the middle

Step 6: curr at index 3, value 1 == pivot, just increase curr

[0, 0, 1, 1, 2, 2]
low=2 curr=4 high=3

Why: All elements processed, done

Result:

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

Annotated Code

DSA Rust

fn dutch_national_flag_partition(arr: &mut [i32], pivot: i32) {
    let mut low = 0;
    let mut curr = 0;
    let mut high = arr.len().saturating_sub(1);

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

fn main() {
    let mut arr = vec![2, 0, 2, 1, 1, 0];
    let pivot = 1;
    dutch_national_flag_partition(&mut arr, pivot);
    for val in arr {
        print!("{} ", val);
    }
    println!();
}

while curr <= high {

loop until curr passes high to process all elements

if arr[curr] < pivot {

if current element is less than pivot, swap to front

arr.swap(low, curr);

swap current with low to move smaller element forward

low += 1; curr += 1;

advance low and curr pointers after placing smaller element

else if arr[curr] == pivot {

if equal to pivot, just move curr forward

curr += 1;

advance curr pointer to check next element

else {

if greater than pivot, swap with high to move larger element to end

arr.swap(curr, high);

swap current with high to move larger element backward

if high == 0 { break; }

prevent underflow when decreasing high

high -= 1;

decrease high pointer after placing larger element

Output

0 0 1 1 2 2 

Complexity Analysis

Time: O(n) because we scan the array once with constant swaps

Space: O(1) because all operations are done in place without extra storage

vs Alternative: Compared to sorting the whole array O(n log n), this is faster and uses no extra space

Edge Cases

empty array

function completes immediately without error

DSA Rust

let mut high = arr.len().saturating_sub(1);

all elements equal to pivot

curr moves through all elements without swaps

DSA Rust

else if arr[curr] == pivot { curr += 1; }

all elements less than pivot

all elements swapped forward, low and curr move together

DSA Rust

if arr[curr] < pivot { arr.swap(low, curr); low += 1; curr += 1; }

all elements greater than pivot

elements swapped to end, high decreases until curr passes high

DSA Rust

else { arr.swap(curr, high); if high == 0 { break; } high -= 1; }

When to Use This Pattern

When you need to sort or group elements into three categories in one pass, use the Dutch National Flag pattern for efficient partitioning.

Common Mistakes

Mistake: Advancing curr pointer after swapping with high without checking the swapped element
Fix: Do not advance curr after swapping with high because the swapped element needs to be checked

Mistake: Not handling empty array causing underflow on high index
Fix: Use saturating_sub or check array length before decrementing high

Summary

Rearranges an array into three parts: less than, equal to, and greater than a pivot value.

Use when you want to partition data into three groups efficiently in one pass.

The key is to maintain three pointers and swap elements to their correct zones without extra space.

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