Sort Colors Two Pointer Dutch Flag in DSA Rust

Mental Model

We separate three groups of colors by moving pointers from both ends and swapping elements to put them in the right place.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls from left and right and swapping them until all reds are left, whites in middle, blues right.

[red, white, blue, white, red, blue]
 ↑left       ↑curr       ↑right

Dry Run Walkthrough

Input: list: [2, 0, 2, 1, 1, 0] where 0=red, 1=white, 2=blue

Goal: Sort the list so all 0s come first, then 1s, then 2s

Step 1: curr=0 points at 2 (blue), right-- to 5, swap with right=5 (0 red), curr stays

[0, 0, 2, 1, 1, 2]
 ↑left  ↑curr          ↑right

Why: Blue should be at right end: decrement right then swap; curr stays to check new value

Step 2: curr=0 points at 0 (red), swap with left=0 (noop), left=1, curr=1

[0, 0, 2, 1, 1, 2]
     ↑left ↑curr       ↑right

Why: Red is correct at left, swap (noop) and move left & curr forward

Step 3: curr=1 points at 0 (red), swap with left=1 (noop), left=2, curr=2

[0, 0, 2, 1, 1, 2]
        ↑left ↑curr    ↑right

Why: Red found, place at left and advance pointers

Step 4: curr=2 points at 2 (blue), right-- to 4, swap with right=4 (1 white), curr stays

[0, 0, 1, 1, 2, 2]
          ↑left ↑curr ↑right

Why: Blue at curr, decrement right then swap to push blue to end

Step 5: curr=2 points at 1 (white), curr moves right to 3

[0, 0, 1, 1, 2, 2]
          ↑left    ↑curr↑right

Why: White is in middle, just move curr forward

Step 6: curr=3 points at 1 (white), curr moves right to 4 (curr >= right, done)

[0, 0, 1, 1, 2, 2]
          ↑left       ↑curr↑right

Why: White in middle, move curr; now curr not < right, loop ends

Result:

[0, 0, 1, 1, 2, 2]
All colors sorted: red, white, blue

Annotated Code

DSA Rust

fn sort_colors(nums: &mut [i32]) {
    let mut left = 0_usize;
    let mut curr = 0_usize;
    let mut right = nums.len();

    while curr < right {
        if nums[curr] == 0 {
            nums.swap(left, curr); // swap red to left
            left += 1; // move left pointer right
            curr += 1; // move curr pointer right
        } else if nums[curr] == 2 {
            right -= 1; // shrink right partition
            nums.swap(curr, right); // swap blue to right
        } else {
            curr += 1; // white in middle, just move curr
        }
    }
}

fn main() {
    let mut colors = vec![2, 0, 2, 1, 1, 0];
    sort_colors(&mut colors);
    for c in colors {
        print!("{} ", c);
    }
    println!();
}

while curr < right {

loop until curr reaches right boundary

if nums[curr] == 0 {

red found, swap to left side

nums.swap(left, curr);

swap red to left pointer position

left += 1; curr += 1;

advance left and curr pointers after placing red

else if nums[curr] == 2 {

blue found, move to right side

right -= 1;

shrink right partition first

nums.swap(curr, right);

swap blue to (new) right pointer position

else { curr += 1; }

white found, just move curr pointer

Output

0 0 1 1 2 2 

Complexity Analysis

Time: O(n) because we scan the list once with pointers moving inward

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to counting sort which uses extra space, this uses constant space and one pass

Edge Cases

empty list

function does nothing and returns immediately

DSA Rust

while curr < right {

list with all same colors

pointers move quickly without swaps, list remains same

DSA Rust

if nums[curr] == 0 { ... } else if nums[curr] == 2 { ... } else { curr += 1; }

list with only two colors

swaps happen only between two colors, algorithm still sorts correctly

DSA Rust

nums.swap(left, curr); and nums.swap(curr, right);

When to Use This Pattern

When you need to sort an array with only three distinct values quickly, use the Dutch Flag two-pointer pattern to sort in one pass and constant space.

Common Mistakes

Mistake: Moving curr pointer after swapping with right without checking the swapped value
Fix: Do not move curr after swapping with right pointer because the swapped element needs to be checked

Summary

Sorts an array of three colors (0,1,2) in one pass using two pointers.

Use when you have exactly three distinct values to sort efficiently.

The key is to keep reds on the left, blues on the right, and whites in the middle by swapping and moving pointers carefully.

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