Remove Duplicates from Sorted Array Two Pointer in DSA Rust - Execution Trace

Concept Flow - Remove Duplicates from Sorted Array Two Pointer

Start with two pointers

↓

Pointer1 at index 0

↓

Compare values at Pointer1 and Pointer2

↓

Repeat until Pointer2 reaches end

↓

Return length = Pointer1 + 1

Use two pointers to scan the array. One pointer tracks unique elements, the other scans ahead to find new unique values to copy.

Execution Sample

DSA Rust

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

This code removes duplicates from a sorted array in place and returns the new length of unique elements.

Execution Table

Step	Operation	Pointer i	Pointer j	Array State	Action
0	Start	0	1	[1, 1, 2, 2, 3]	Initialize pointers i=0, j=1
1	Compare nums[j] and nums[i]	0	1	[1, 1, 2, 2, 3]	nums[1]=1 == nums[0]=1, duplicate found, move j
2	Move j forward	0	2	[1, 1, 2, 2, 3]	j=2
3	Compare nums[j] and nums[i]	0	2	[1, 1, 2, 2, 3]	nums[2]=2 != nums[0]=1, unique found
4	Move i forward and copy	1	2	[1, 2, 2, 2, 3]	i=1, nums[1]=nums[2]=2
5	Move j forward	1	3	[1, 2, 2, 2, 3]	j=3
6	Compare nums[j] and nums[i]	1	3	[1, 2, 2, 2, 3]	nums[3]=2 == nums[1]=2, duplicate found, move j
7	Move j forward	1	4	[1, 2, 2, 2, 3]	j=4
8	Compare nums[j] and nums[i]	1	4	[1, 2, 2, 2, 3]	nums[4]=3 != nums[1]=2, unique found
9	Move i forward and copy	2	4	[1, 2, 3, 2, 3]	i=2, nums[2]=nums[4]=3
10	j reaches end	2	5	[1, 2, 3, 2, 3]	j=5 (end), stop
11	Return length	2	5	[1, 2, 3, 2, 3]	Length = i + 1 = 3

💡 Pointer j reached the end of the array, all unique elements processed.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 6	After Step 9	Final
i	0	0	0	1	1	2	2
j	1	1	2	2	3	4	5
nums	[1,1,2,2,3]	[1,1,2,2,3]	[1,1,2,2,3]	[1,2,2,2,3]	[1,2,2,2,3]	[1,2,3,2,3]	[1,2,3,2,3]

Key Moments - 3 Insights

Why do we move pointer i only when we find a new unique element?

Pointer i marks the position of last unique element. We move it only when a new unique value is found to overwrite the next position with that unique value, as shown in steps 4 and 9.

Why does pointer j start from 1 and not 0?

Pointer j starts from 1 because pointer i is at 0 initially, and we compare nums[j] with nums[i]. Starting j at 1 avoids comparing the first element with itself, as seen in step 0.

What happens if the array is empty?

If the array is empty, the function returns 0 immediately without entering the loop, as the initial check prevents any operations.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the value of pointer i?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Pointer i' column at step 4 in the execution_table.

At which step does the array first change its state?

A Step 4

B Step 3

C Step 1

D Step 6

💡 Hint

Look at the 'Array State' column and see when the first modification occurs.

If the input array was empty, what would the function return?

A Length of array

B 1

C 0

D Error

💡 Hint

Refer to the initial check in the code sample and the key moment about empty arrays.

Concept Snapshot

Remove duplicates from a sorted array using two pointers:
- Pointer i tracks last unique element index
- Pointer j scans ahead for new unique values
- When nums[j] != nums[i], increment i and copy nums[j]
- Continue until j reaches end
- Return i + 1 as new length
- Works in-place with O(1) extra space

Full Transcript

This concept uses two pointers to remove duplicates from a sorted array. Pointer i starts at index 0 and marks the position of the last unique element. Pointer j starts at index 1 and scans the array. When nums[j] is different from nums[i], pointer i moves forward and the unique value at nums[j] is copied to nums[i]. This process continues until pointer j reaches the end of the array. The function returns i + 1, which is the count of unique elements. The array is modified in place, and duplicates are overwritten. If the array is empty, the function returns 0 immediately. This approach uses constant extra space and linear time.

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