Remove Duplicates from Sorted Array Two Pointer in DSA Rust - Deep Dive

Overview - Remove Duplicates from Sorted Array Two Pointer

What is it?

Removing duplicates from a sorted array means changing the array so that each number appears only once, without changing the order. The two-pointer technique uses two markers to scan and update the array efficiently. This method modifies the array in place, so no extra space is needed. It returns the new length of the array after duplicates are removed.

Why it matters

Without this method, removing duplicates would require extra space or multiple scans, making programs slower and more memory-heavy. Efficiently removing duplicates is important in many real-world tasks like cleaning data, searching, or preparing lists for further processing. This technique saves time and memory, making software faster and more efficient.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn about other two-pointer problems, like merging arrays or partitioning. This topic is a stepping stone to mastering in-place algorithms and optimizing space usage.

Mental Model

Core Idea

Use two pointers to track unique elements and overwrite duplicates in a sorted array, keeping only one copy of each number.

Think of it like...

Imagine walking through a line of people sorted by height, and you want to keep only one person of each height. One hand points to the last unique person you kept, and the other hand scans ahead to find the next new height to keep.

Sorted Array: [1, 1, 2, 3, 3, 4]

Pointers:
  i -> last unique index
  j -> current scanning index

Process:
Start: i=0, j=1

Step 1: Compare arr[i]=1 and arr[j]=1 (same) -> skip j
Step 2: j=2, arr[j]=2 != arr[i]=1 -> i=1, arr[i]=2
Step 3: j=3, arr[j]=3 != arr[i]=2 -> i=2, arr[i]=3
Step 4: j=4, arr[j]=3 == arr[i]=3 -> skip j
Step 5: j=5, arr[j]=4 != arr[i]=3 -> i=3, arr[i]=4

Result array (first i+1 elements): [1, 2, 3, 4]

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why duplicates appear consecutively.

A sorted array is a list of numbers arranged from smallest to largest. Because it's sorted, any duplicates will be next to each other. For example, in [1, 1, 2, 3, 3], the duplicates 1 and 3 appear side by side. This property helps us find duplicates easily by comparing neighbors.

Result

You know that duplicates in a sorted array are always next to each other.

Understanding that duplicates are consecutive in sorted arrays allows us to check only neighbors instead of the whole array.

2

Foundation

Basic Two Pointer Concept

Concept: Introduce two pointers to scan and update the array simultaneously.

Two pointers are like two fingers moving over the array. One pointer (i) marks the position of the last unique number found. The other pointer (j) scans ahead to find new unique numbers. When j finds a new number, we move i forward and copy that number there.

Result

You can track unique elements and update the array in one pass.

Using two pointers lets us process the array efficiently without extra space.

3

Intermediate

Implementing Two Pointer in Rust

🤔Before reading on: do you think the first pointer should start at index 0 or 1? Commit to your answer.

Concept: Write Rust code that uses two pointers to remove duplicates in place.

fn remove_duplicates(nums: &mut Vec) -> 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 } // Example usage: // let mut arr = vec![1,1,2,3,3,4]; // let len = remove_duplicates(&mut arr); // arr.truncate(len); // println!("{:?}", arr); // Output: [1, 2, 3, 4]

Result

The function returns the new length and modifies the array to contain only unique elements at the start.

Knowing where to start the first pointer avoids overwriting the first element and ensures all unique elements are kept.

4

Intermediate

Handling Edge Cases

🤔Before reading on: what should the function return if the array is empty? Commit to your answer.

Concept: Consider empty arrays and arrays with one element to avoid errors.

If the array is empty, return 0 because there are no elements. If it has one element, return 1 because it's already unique. The code checks for empty arrays at the start and handles them immediately to prevent errors during the loop.

Result

The function safely handles empty and single-element arrays without crashing.

Handling edge cases prevents runtime errors and makes the function robust.

5

Intermediate

In-place Modification Benefits

Concept: Understand why modifying the array in place is efficient.

Instead of creating a new array, we overwrite duplicates in the original array. This saves memory because no extra space is needed. It also speeds up the program since we avoid copying data multiple times.

Result

The array is updated without extra memory, improving performance.

In-place modification is a key technique for optimizing space in algorithms.

6

Advanced

Time and Space Complexity Analysis

🤔Before reading on: do you think this algorithm runs in linear or quadratic time? Commit to your answer.

Concept: Analyze how fast and memory-efficient the two-pointer method is.

The algorithm scans the array once, so it runs in O(n) time, where n is the array length. It uses only a few variables, so space complexity is O(1), constant space. This is optimal for this problem because every element must be checked at least once.

Result

You understand the algorithm is both fast and memory-efficient.

Knowing the complexity helps you choose this method for large datasets where speed and memory matter.

7

Expert

Surprising Behavior with Non-Sorted Arrays

🤔Before reading on: do you think this method works correctly on unsorted arrays? Commit to your answer.

Concept: Explore what happens if the array is not sorted and why sorting is crucial.

If the array is not sorted, duplicates may not be next to each other. The two-pointer method will fail to remove all duplicates because it only compares neighbors. For example, [2,1,2] would become [2,1,2] with length 3, still containing duplicates. Sorting first or using a different method is necessary for unsorted arrays.

Result

You realize the method depends on sorted input and fails otherwise.

Understanding input requirements prevents bugs and misuse of the algorithm.

Under the Hood

The two-pointer method works by maintaining a slow pointer (i) that marks the position of the last unique element and a fast pointer (j) that scans through the array. When the fast pointer finds a new unique element different from the one at the slow pointer, the slow pointer moves forward, and the new element is copied there. This overwrites duplicates and compacts unique elements at the front. The rest of the array remains unchanged but is ignored after the new length.

Why designed this way?

This method was designed to optimize space by avoiding extra arrays and to leverage the sorted property of the input. Alternatives like using hash sets require extra memory. The two-pointer approach balances simplicity, speed, and memory efficiency, making it ideal for in-place operations on sorted data.

Array: [1, 1, 2, 3, 3, 4]

Start:
 i=0 (points to 1)
 j=1 (points to 1)

Loop:
 j moves forward:
  - If nums[j] != nums[i], increment i and copy nums[j] to nums[i]

Result:
 i=3 (points to 4)
 Array front: [1, 2, 3, 4]

Discard rest beyond i

Myth Busters - 3 Common Misconceptions

Quick: Does this method remove duplicates from any array, sorted or not? Commit yes or no.

Common Belief: This two-pointer method removes duplicates from any array, regardless of order.

Reality: It only works correctly on sorted arrays because duplicates must be adjacent to detect them by comparing neighbors.

Why it matters: Using this method on unsorted arrays leads to incorrect results, leaving duplicates behind and causing bugs.

Quick: Does the method require extra memory proportional to the array size? Commit yes or no.

Common Belief: Removing duplicates always needs extra memory to store unique elements.

Reality: This method removes duplicates in place using constant extra space, without allocating new arrays.

Why it matters: Knowing this helps write memory-efficient code, especially important in systems with limited resources.

Quick: After running the method, is the entire array guaranteed to be free of duplicates? Commit yes or no.

Common Belief: The entire array is free of duplicates after the method runs.

Reality: Only the first part of the array up to the returned length is guaranteed duplicate-free; the rest remains unchanged and may contain duplicates.

Why it matters: Misunderstanding this can cause errors if the leftover part of the array is mistakenly used.

Expert Zone

1

The returned length indicates how many unique elements are at the start, but the array beyond that length is not cleared or modified, which can cause confusion if not handled.

2

In Rust, using Vec::truncate with the returned length safely removes the leftover duplicates from the vector, preventing accidental use.

3

The two-pointer technique can be adapted for similar problems like removing duplicates from linked lists or merging sorted arrays, showing its versatility.

When NOT to use

Do not use this method on unsorted arrays; instead, sort first or use a hash set to track duplicates. Also, if preserving the original array order without sorting is required, alternative methods like hash-based filtering are better.

Production Patterns

In production, this method is used in data cleaning pipelines where sorted data needs deduplication before analysis. It's also common in embedded systems where memory is limited, and in performance-critical code where minimizing allocations is essential.

Connections

Two Pointer Technique

This problem is a classic example of the two pointer technique applied to arrays.

Mastering this problem helps understand how two pointers can solve many array and string problems efficiently.

In-place Algorithms

This method is a practical example of modifying data in place without extra space.

Understanding in-place algorithms is crucial for writing memory-efficient code in constrained environments.

Data Cleaning in Data Science

Removing duplicates is a fundamental step in cleaning datasets before analysis.

Knowing this algorithm helps data scientists preprocess data efficiently, improving model quality and performance.

Common Pitfalls

#1 Assuming the entire array is duplicate-free after the function returns.

Wrong approach:

let mut arr = vec![1,1,2,3,3,4];
let len = remove_duplicates(&mut arr);
println!("{:?}", arr); // Prints full array without truncation

Correct approach:

let mut arr = vec![1,1,2,3,3,4];
let len = remove_duplicates(&mut arr);
arr.truncate(len);
println!("{:?}", arr); // Prints only unique elements

Root cause:

Not truncating the vector after getting the new length leaves old duplicate elements visible.

#2 Using this method on an unsorted array expecting correct results.

Wrong approach:

let mut arr = vec![2,1,2];
let len = remove_duplicates(&mut arr);
arr.truncate(len);
println!("{:?}", arr); // Incorrect output with duplicates

Correct approach:

arr.sort();
let len = remove_duplicates(&mut arr);
arr.truncate(len);
println!("{:?}", arr); // Correct unique sorted output

Root cause:

The algorithm relies on sorted input; skipping sorting breaks correctness.

#3 Starting the first pointer at index 1 instead of 0.

Wrong approach:

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

Correct approach:

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

Root cause:

Starting at 1 skips the first element and causes incorrect overwriting.

Key Takeaways

Removing duplicates from a sorted array can be done efficiently using two pointers without extra space.

The first pointer tracks the last unique element, while the second scans for new unique elements to overwrite duplicates.

This method requires the array to be sorted because duplicates must be adjacent to detect them.

After processing, only the first part of the array up to the returned length is guaranteed to be duplicate-free.

Handling edge cases and truncating the array after removal are essential for correct and safe usage.

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