Sort Colors Two Pointer Dutch Flag in DSA Rust - Execution Trace

Concept Flow - Sort Colors Two Pointer Dutch Flag

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

↓

Check mid <= high?

No→Done

Yes↓

Inspect nums[mid

↓

Swap nums[low

↓

Repeat check mid <= high?

We use three pointers low, mid, and high to sort colors by swapping 0s to the front and 2s to the end, moving mid through the array.

Execution Sample

DSA Rust

fn sort_colors(nums: &mut [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; },
            _ => {}
        }
    }
}

Sorts an array containing 0,1,2 by moving 0s left, 2s right, and 1s stay in middle using three pointers.

Execution Table

Step	Operation	Pointers (low, mid, high)	Array State	Pointer Changes	Visual State
1	Initialize pointers	(0, 0, 5)	[2, 0, 2, 1, 1, 0]	None	low=0, mid=0, high=5; array unchanged
2	Inspect nums[mid]=2	(0, 0, 5)	[2, 0, 2, 1, 1, 0]	Swap nums[mid] and nums[high], high=4	Swap indices 0 and 5; array=[0,0,2,1,1,2]; high=4
3	Inspect nums[mid]=0	(0, 0, 4)	[0, 0, 2, 1, 1, 2]	Swap nums[low] and nums[mid], low=1, mid=1	Swap indices 0 and 0; array unchanged; low=1, mid=1
4	Inspect nums[mid]=0	(1, 1, 4)	[0, 0, 2, 1, 1, 2]	Swap nums[low] and nums[mid], low=2, mid=2	Swap indices 1 and 1; array unchanged; low=2, mid=2
5	Inspect nums[mid]=2	(2, 2, 4)	[0, 0, 2, 1, 1, 2]	Swap nums[mid] and nums[high], high=3	Swap indices 2 and 4; array=[0,0,1,1,2,2]; high=3
6	Inspect nums[mid]=1	(2, 2, 3)	[0, 0, 1, 1, 2, 2]	mid=3	mid=3; array unchanged
7	Inspect nums[mid]=1	(2, 3, 3)	[0, 0, 1, 1, 2, 2]	mid=4	mid=4; array unchanged
8	Check mid <= high? mid=4, high=3	(2, 4, 3)	[0, 0, 1, 1, 2, 2]	No - exit loop	Sorting complete; final array=[0,0,1,1,2,2]

💡 mid (4) > high (3), loop ends; array is sorted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
low	0	0	1	2	2	2	2	2
mid	0	0	1	2	2	3	4	4
high	5	4	4	4	3	3	3	3
nums	[2,0,2,1,1,0]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]

Key Moments - 3 Insights

Why do we not increment mid when nums[mid] is 2?

Because after swapping nums[mid] with nums[high], the new nums[mid] might be 0, 1, or 2. We must check it again before moving mid forward. See step 2 and 5 in execution_table.

Why do we increment both low and mid when nums[mid] is 0?

Swapping nums[low] and nums[mid] places 0 at the front. We can safely move both pointers forward because everything before low is sorted. See steps 3 and 4.

What stops the loop from running forever?

The loop condition mid <= high ensures we stop when mid passes high. Each step moves mid forward or high backward, guaranteeing termination. See step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the array state after swapping?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 5 in execution_table.

At which step does mid first increment without swapping?

A Step 3

B Step 2

C Step 6

D Step 5

💡 Hint

Look for steps where 'mid=...' is the only pointer change without swaps in execution_table.

If nums[mid] is 1, how does the algorithm proceed?

A Increment mid only

B Swap with nums[low] and increment low and mid

C Swap with nums[high] and decrement high

D Stop the loop

💡 Hint

See the match case for 1 in the code and steps 6 and 7 in execution_table.

Concept Snapshot

Sort Colors (Dutch Flag) uses three pointers: low, mid, high.
- low: boundary for 0s
- mid: current element
- high: boundary for 2s
Process:
- If nums[mid]==0: swap with nums[low], increment low and mid
- If nums[mid]==1: increment mid
- If nums[mid]==2: swap with nums[high], decrement high
Loop until mid > high.

Full Transcript

This visualization shows how the Sort Colors algorithm works using the Dutch Flag approach with two pointers. We start with three pointers: low, mid, and high. Initially, low and mid are at the start of the array, and high is at the end. We check the element at mid. If it is 0, we swap it with the element at low and move both pointers forward. If it is 1, we just move mid forward. If it is 2, we swap it with the element at high and move high backward, but we do not move mid because the swapped element needs to be checked. This process continues until mid passes high, ensuring all 0s are at the front, 1s in the middle, and 2s at the end. The execution table traces each step with pointer positions and array state changes, helping learners see exactly how the array is sorted step-by-step.

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