Remove Duplicates from Sorted Array Two Pointer in DSA Rust

Mental Model

Use two pointers to overwrite duplicates in a sorted array, keeping only unique elements at the start.

Analogy: Imagine cleaning a row of books on a shelf where duplicates are removed by sliding unique books forward to fill gaps.

[1, 1, 2, 3, 3, 4, 5]
 ↑   ↑
 slow fast

Dry Run Walkthrough

Input: array: [1, 1, 2, 3, 3, 4, 5]

Goal: Remove duplicates in-place so the start of the array contains unique elements only

Step 1: Initialize slow at index 0, fast at index 1

[1, 1, 2, 3, 3, 4, 5]
 slow=0 ↑ fast=1 ↑

Why: Start comparing from the second element to find duplicates

Step 2: fast points to 1, same as slow value, skip fast forward

[1, 1, 2, 3, 3, 4, 5]
 slow=0 ↑ fast=2 ↑

Why: Duplicate found, do not move slow, just advance fast

Step 3: fast points to 2, different from slow value, increment slow and copy fast value

[1, 2, 2, 3, 3, 4, 5]
 slow=1 ↑ fast=2 ↑

Why: Found new unique value, move slow forward and overwrite

Step 4: fast moves to 3, different from slow value 2, increment slow and copy fast value

[1, 2, 3, 3, 3, 4, 5]
 slow=2 ↑ fast=3 ↑

Why: Another unique value found, update slow position

Step 5: fast points to 3 again, same as slow value, skip fast forward

[1, 2, 3, 3, 3, 4, 5]
 slow=2 ↑ fast=4 ↑

Why: Duplicate detected, do not move slow

Step 6: fast points to 4, different from slow value, increment slow and copy fast value

[1, 2, 3, 4, 3, 4, 5]
 slow=3 ↑ fast=5 ↑

Why: Unique value found, move slow forward and overwrite

Step 7: fast points to 5, different from slow value, increment slow and copy fast value

[1, 2, 3, 4, 5, 4, 5]
 slow=4 ↑ fast=6 ↑

Why: Last unique value copied

Result:

[1, 2, 3, 4, 5, 4, 5]
Unique elements count: 5

Annotated Code

DSA Rust

fn remove_duplicates(nums: &mut Vec<i32>) -> usize {
    if nums.is_empty() {
        return 0;
    }
    let mut slow = 0;
    for fast in 1..nums.len() {
        if nums[fast] != nums[slow] {
            slow += 1;
            nums[slow] = nums[fast];
        }
    }
    slow + 1
}

fn main() {
    let mut nums = vec![1, 1, 2, 3, 3, 4, 5];
    let len = remove_duplicates(&mut nums);
    print!("{}\n", nums[..len].iter().map(|x| x.to_string()).collect::<Vec<_>>().join(", "));
    print!("Unique elements count: {}\n", len);
}

for fast in 1..nums.len() {

iterate fast pointer from second element to end

if nums[fast] != nums[slow] {

check if current fast value is different from slow value

slow += 1;

increment slow pointer to next unique position

nums[slow] = nums[fast];

overwrite slow position with new unique value

Output

1, 2, 3, 4, 5

Unique elements count: 5

Complexity Analysis

Time: O(n) because we scan the array once with two pointers

Space: O(1) because we modify the array in place without extra storage

vs Alternative: Compared to creating a new array for unique elements, this approach saves space by overwriting duplicates in place

Edge Cases

empty array

returns 0 immediately, no processing needed

DSA Rust

if nums.is_empty() { return 0; }

array with all duplicates

returns 1, only one unique element remains at start

DSA Rust

if nums[fast] != nums[slow] { ... }

array with no duplicates

returns original length, array unchanged

DSA Rust

if nums[fast] != nums[slow] { ... }

When to Use This Pattern

When you see a sorted array and need to remove duplicates in place, use the two pointer pattern to overwrite duplicates efficiently.

Common Mistakes

Mistake: Incrementing slow pointer even when duplicate is found
Fix: Only increment slow pointer when a new unique element is found (nums[fast] != nums[slow])

Summary

Removes duplicates from a sorted array by overwriting duplicates with unique values using two pointers.

Use when you want to remove duplicates in place without extra space in a sorted array.

The key insight is to use one pointer to track unique elements and another to explore new values.

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

A. To sort the array before removing duplicates

B. To efficiently track unique elements and overwrite duplicates in-place

C. To create a new array with unique elements

D. To count the total number of duplicates in the array

Solution

1. Step 1: Understand the two-pointer approach

   One pointer tracks the position to place the next unique element, the other scans the array.

2. Step 2: Purpose of pointers in-place

   This method avoids extra space by overwriting duplicates directly in the original array.

3. Final Answer:

   To efficiently track unique elements and overwrite duplicates in-place -> Option B

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers move to overwrite duplicates without extra space [OK]

Common Mistakes:

• Thinking two pointers create a new array
• Assuming sorting is needed again
• Counting duplicates instead of removing

2. Which of the following Rust code snippets correctly initializes two pointers for the Remove Duplicates problem?

easy

A. let mut i = 1; let mut j = 0;

B. let mut i = 0; let mut j = 1;

C. let i = 1; let j = 0;

D. let i = 0; let j = 0;

Solution

1. Step 1: Identify pointer roles

   Pointer i tracks last unique index, starting at 0; j scans from 1.

2. Step 2: Match initialization

   Correct initialization is let mut i = 1; let mut j = 0; to start comparing from second element.

3. Final Answer:

   let mut i = 1; let mut j = 0; -> Option A

4. Quick Check:

   i=1, j=0 starts scanning correctly [OK]

Hint: Start i at 1 and j at 0 to compare adjacent elements [OK]

Common Mistakes:

• Swapping i and j initialization
• Not using mutable variables
• Starting both pointers at 0

3. What will be the content of the array after running the two-pointer duplicate removal on let mut nums = vec![1, 1, 2, 3, 3];?

medium

A. [1, 2, 3, 3, 3]

B. [1, 1, 2, 3, 3]

C. [1, 2, 3, _, _]

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

Solution

1. Step 1: Apply two-pointer logic

   Start with i=0, j=1; compare nums[j] with nums[i]. When different, increment i and copy nums[j].

2. Step 2: Trace array changes

   nums changes to [1, 2, 3, 3, 3], but only first 3 elements are unique; rest are leftover values.

3. Final Answer:

   [1, 2, 3, _, _] -> Option C

4. Quick Check:

   Unique elements at start, duplicates ignored [OK]

Hint: Unique elements fill front; leftover values remain unchanged [OK]

Common Mistakes:

• Assuming duplicates are removed from array length
• Expecting zeros instead of leftover values
• Not understanding in-place overwrite

4. Identify the bug in this Rust code snippet for removing duplicates from a sorted array:

let mut i = 0;
for j in 1..nums.len() {
    if nums[i] == nums[j] {
        i += 1;
        nums[i] = nums[j];
    }
}

medium

A. Pointer i should not be incremented inside the if block

B. The loop range should start from 0, not 1

C. nums[i] should be compared with nums[i-1], not nums[j]

D. The condition should check for inequality, not equality

Solution

1. Step 1: Analyze the if condition

   The code increments i and copies nums[j] only when nums[i] == nums[j], which is wrong.

2. Step 2: Correct condition logic

   We want to copy nums[j] only when nums[j] != nums[i], meaning a new unique element found.

3. Final Answer:

   The condition should check for inequality, not equality -> Option D

4. Quick Check:

   Copy unique elements when different [OK]

Hint: Copy when elements differ, not when equal [OK]

Common Mistakes:

• Incrementing i on duplicates
• Wrong comparison operator
• Loop starting index confusion

5. Given a sorted vector nums with possible duplicates, how would you modify the two-pointer approach to return the count of unique elements and also ensure the first part of the vector contains only these unique elements in Rust?

hard

A. Use two pointers i=0, j=1; increment i and copy nums[j] when nums[j] != nums[i]; return i+1 as count

B. Use a HashSet to collect unique elements, then overwrite nums with the set; return set size

C. Sort the vector again after removing duplicates; return length of sorted vector

D. Iterate with one pointer, remove duplicates by shifting elements left; return original length minus duplicates

Solution

1. Step 1: Initialize pointers and iterate

   Set i=0 for last unique index, j=1 to scan; compare nums[j] with nums[i].

2. Step 2: Copy unique elements and count

   If nums[j] != nums[i], increment i and copy nums[j] to nums[i]. After loop, unique count is i+1.

3. Final Answer:

   Use two pointers i=0, j=1; increment i and copy nums[j] when nums[j] != nums[i]; return i+1 as count -> Option A

4. Quick Check:

   Two-pointer overwrite returns unique count [OK]

Hint: Increment i only on new unique element, return i+1 [OK]

Common Mistakes:

• Using extra space like HashSet unnecessarily
• Re-sorting after removal
• Incorrect count calculation