Dutch National Flag Three Way Partition in DSA Rust - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Initialize pointers: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Inspect arr[mid

↓

Swap arr[low

↓

mid++

↓

Swap arr[mid

↓

Repeat check mid <= high?

We use three pointers low, mid, and high to partition the array into three parts: 0s, 1s, and 2s by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA Rust

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

This code sorts an array containing only 0s, 1s, and 2s by placing all 0s first, then 1s, then 2s using three pointers and swaps.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes	Visual State
1	Start	0	0	7	[2, 0, 2, 1, 1, 0, 0, 2]	Initial pointers	low=0, mid=0, high=7
2	Inspect arr[mid]=2	0	0	7	[2, 0, 2, 1, 1, 0, 0, 2]	Swap arr[mid] and arr[high], high--	Swap arr[0]<->arr[7], high=6
3	After swap	0	0	6	[2, 0, 2, 1, 1, 0, 0, 2]	Array unchanged as both 2s swapped	low=0, mid=0, high=6
4	Inspect arr[mid]=2	0	0	6	[2, 0, 2, 1, 1, 0, 0, 2]	Swap arr[mid] and arr[high], high--	Swap arr[0]<->arr[6], high=5
5	After swap	0	0	5	[0, 0, 2, 1, 1, 0, 2, 2]	Array updated	low=0, mid=0, high=5
6	Inspect arr[mid]=0	0	0	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[low] and arr[mid], low++, mid++	Swap arr[0]<->arr[0], low=1, mid=1
7	After swap	1	1	5	[0, 0, 2, 1, 1, 0, 2, 2]	Pointers moved	low=1, mid=1, high=5
8	Inspect arr[mid]=0	1	1	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[low] and arr[mid], low++, mid++	Swap arr[1]<->arr[1], low=2, mid=2
9	After swap	2	2	5	[0, 0, 2, 1, 1, 0, 2, 2]	Pointers moved	low=2, mid=2, high=5
10	Inspect arr[mid]=2	2	2	5	[0, 0, 2, 1, 1, 0, 2, 2]	Swap arr[mid] and arr[high], high--	Swap arr[2]<->arr[5], high=4
11	After swap	2	2	4	[0, 0, 0, 1, 1, 2, 2, 2]	Array updated	low=2, mid=2, high=4
12	Inspect arr[mid]=0	2	2	4	[0, 0, 0, 1, 1, 2, 2, 2]	Swap arr[low] and arr[mid], low++, mid++	Swap arr[2]<->arr[2], low=3, mid=3
13	After swap	3	3	4	[0, 0, 0, 1, 1, 2, 2, 2]	Pointers moved	low=3, mid=3, high=4
14	Inspect arr[mid]=1	3	3	4	[0, 0, 0, 1, 1, 2, 2, 2]	mid++	mid=4
15	Inspect arr[mid]=1	3	4	4	[0, 0, 0, 1, 1, 2, 2, 2]	mid++	mid=5
16	Check mid <= high	3	5	4	[0, 0, 0, 1, 1, 2, 2, 2]	mid=5 > high=4, stop	Done

💡 mid (5) > high (4), so partitioning is complete

Variable Tracker

Variable	Start	After 2	After 4	After 6	After 8	After 10	After 12	After 15	Final
low	0	0	0	1	2	2	3	3	3
mid	0	0	0	1	2	2	3	5	5
high	7	6	5	5	5	4	4	4	4
Array	[2,0,2,1,1,0,0,2]	[2,0,2,1,1,0,0,2]	[0,0,2,1,1,0,2,2]	[0,0,2,1,1,0,2,2]	[0,0,2,1,1,0,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]	[0,0,0,1,1,2,2,2]

Key Moments - 3 Insights

Why do we not increment mid when swapping with high pointer?

When arr[mid] is 2, we swap with arr[high] and decrease high, but do not increment mid because the swapped element at mid is unprocessed and needs checking (see steps 10-11).

Why do we increment both low and mid when swapping 0s?

When arr[mid] is 0, swapping with arr[low] places 0 in correct position, so we move both pointers forward to process next elements (see steps 6-9).

What stops the loop from running forever?

The loop stops when mid passes high (step 16), ensuring all elements are partitioned correctly.

Visual Quiz - 3 Questions

Look at the execution table at step 10, what is the value of 'high' after the swap?

A 4

B 5

C 6

D 3

💡 Hint

Check the 'high' column in the execution_table row for step 10.

At which step does 'mid' first increment without swapping?

A Step 6

B Step 14

C Step 10

D Step 2

💡 Hint

Look for steps where operation is 'Inspect arr[mid]=1' and only mid increments.

If the array started with all 0s, how would the pointer 'high' behave?

A It would move right each time.

B It would move left each time.

C It would stay at the end and never move.

D It would move randomly.

💡 Hint

Refer to variable_tracker and note that 'high' only moves when swapping 2s.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- low: boundary for 0s, high: boundary for 2s
- mid scans array:
  * If 0: swap with low, increment low and mid
  * If 1: just increment mid
  * If 2: swap with high, decrement high
- Stop when mid > high
- Sorts array of 0s,1s,2s in one pass

Full Transcript

The Dutch National Flag algorithm partitions an array containing only 0s, 1s, and 2s into three sections. It uses three pointers: low, mid, and high. Initially, low and mid start at the beginning, and high at the end. We check the element at mid: if it's 0, we swap it with the element at low and move both pointers forward; if it's 1, we just move mid forward; if it's 2, we swap it with the element at high and move high backward. We repeat this until mid passes high. This ensures all 0s are at the start, 1s in the middle, and 2s at the end, sorting the array in one pass efficiently.

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