Remove Duplicates from Sorted Array Two Pointer in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the two-pointer technique for removing duplicates from a sorted array?

Use one pointer to track the position of unique elements and another to scan through the array, copying unique elements forward to overwrite duplicates.

beginner

Why does the two-pointer method work efficiently on a sorted array?

Because duplicates are adjacent, the method can easily detect and skip duplicates by comparing current and previous elements.

intermediate

In Rust, what is a safe way to modify an array in place when removing duplicates?

Use mutable slices and update elements by index while keeping track of the unique count, avoiding resizing or reallocations.

beginner

What does the returned value represent in the remove duplicates function using two pointers?

It represents the new length of the array after duplicates are removed, indicating how many unique elements remain at the start.

beginner

How does the two-pointer approach avoid extra space usage?

It modifies the array in place by overwriting duplicates, so no additional arrays or data structures are needed.

What is the initial position of the 'slow' pointer in the two-pointer method for removing duplicates?

A 0

B 1

C Length of array - 1

D Length of array

The slow pointer starts at index 0 to track the position of the last unique element.

Why can we skip elements when the current element equals the previous one in a sorted array?

A Because the array is unsorted

B Because duplicates are adjacent and already counted

C Because the element is unique

D Because the array is empty

Duplicates appear next to each other in a sorted array, so we can skip repeated elements.

What does the 'fast' pointer do in the two-pointer approach?

A Deletes duplicates

B Tracks the last unique element

C Sorts the array

D Scans through the array to find unique elements

The fast pointer moves forward to find new unique elements to copy.

What is the time complexity of removing duplicates from a sorted array using two pointers?

A O(1)

B O(n^2)

C O(n)

D O(log n)

Each element is visited once, so the time complexity is linear.

After removing duplicates, where are the unique elements located in the array?

A At the beginning of the array

B At the end of the array

C Scattered randomly

D Removed completely

Unique elements are moved to the front of the array in order.

Explain step-by-step how the two-pointer technique removes duplicates from a sorted array.

Think about how one pointer tracks unique elements and the other scans.

Describe how you would implement the remove duplicates function in Rust using the two-pointer approach.

Focus on in-place modification and indexing.

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