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

Overview - Remove Duplicates from Sorted Array Two Pointer

What is it?

This topic teaches how to remove duplicate numbers from a sorted list of numbers using two pointers. The goal is to keep only unique numbers and shift them to the front of the list. The method changes the list in place without using extra space for another list.

Why it matters

Removing duplicates helps clean data and makes searching or processing faster. Without this, programs might waste time handling repeated values or use extra memory to store unique items separately. This technique is important in many real-world tasks like filtering contacts, logs, or sorted data streams.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn about more complex array problems, like sliding windows or merging sorted lists.

Mental Model

Core Idea

Use two pointers to track unique elements and overwrite duplicates by moving unique values forward in the array.

Think of it like...

Imagine sorting your bookshelf and removing duplicate books by sliding unique books to the left side, leaving duplicates behind without needing a new shelf.

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

Pointers:
  i -> position of last unique element found
  j -> scans through the array

Process:
Start: i=0, j=1

[1, 1, 2, 3, 3, 4]
  ^  ^
  i  j

If arr[j] != arr[i], move i forward and copy arr[j] to arr[i]

Result after processing:
[1, 2, 3, 4, _, _]
Unique count = i + 1 = 4

Build-Up - 7 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why duplicates appear next to each other.

A sorted array is a list where numbers are arranged from smallest to largest. Because of this order, any duplicates will be next to each other. For example, in [1, 1, 2, 3, 3], the duplicates 1 and 3 are side by side.

Result

Duplicates are grouped together, making it easier to find and remove them.

Knowing duplicates are adjacent lets us scan the array once and compare neighbors to find duplicates efficiently.

2

Foundation

Basic Array Traversal

Concept: Learn how to move through an array using a loop and access elements by index.

We use a loop to visit each element in the array from start to end. For example, for (int i = 0; i < n; i++) lets us look at every element one by one.

Result

You can check or change each element in order.

Mastering array traversal is essential because all array problems require visiting elements systematically.

3

Intermediate

Two Pointer Technique Introduction

Concept: Use two pointers to track positions in the array for comparison and modification.

We keep one pointer (i) at the last unique element found and another pointer (j) scanning ahead. When arr[j] is different from arr[i], we move i forward and copy arr[j] there.

Result

Unique elements are moved to the front, duplicates are skipped.

Two pointers let us process the array in one pass without extra space, improving efficiency.

4

Intermediate

In-place Modification Without Extra Space

Concept: Change the array directly to save memory instead of creating a new array.

Instead of making a new list, we overwrite duplicates by copying unique values forward. This keeps memory use low and is faster.

Result

The original array holds only unique values at the start after processing.

In-place changes are important for large data where extra memory is costly or unavailable.

5

Intermediate

Implementing Two Pointer Algorithm in C++

🤔Before reading on: do you think the first pointer moves only when a new unique element is found, or every step? Commit to your answer.

Concept: Write code that uses two pointers to remove duplicates and return the count of unique elements.

int removeDuplicates(vector& nums) { if (nums.empty()) return 0; int i = 0; for (int j = 1; j < nums.size(); j++) { if (nums[j] != nums[i]) { i++; nums[i] = nums[j]; } } return i + 1; } // Example usage: // nums = [1,1,2,3,3] // After function call, nums = [1,2,3,3,3], return 3

Result

Function returns 3 and first 3 elements are unique: [1, 2, 3]

Knowing the first pointer moves only when a new unique element is found helps avoid unnecessary overwrites and keeps the array compact.

6

Advanced

Handling Edge Cases and Empty Arrays

🤔Before reading on: do you think the algorithm works correctly if the array is empty or has one element? Commit to your answer.

Concept: Make sure the code handles arrays with zero or one element without errors.

Check if the array is empty at the start and return 0. If only one element, return 1 immediately. This prevents errors like accessing elements that don't exist.

Result

Algorithm safely returns 0 for empty and 1 for single-element arrays.

Handling edge cases prevents crashes and ensures the algorithm is robust for all inputs.

7

Expert

Why Two Pointer Beats Other Methods

🤔Before reading on: do you think using extra space for a set is faster or slower than two pointers? Commit to your answer.

Concept: Compare two pointer method with using extra data structures like sets to remove duplicates.

Using a set requires extra memory and may not keep order. Two pointers use constant space and preserve order. Also, two pointers run in O(n) time with one pass, while sets may have overhead.

Result

Two pointer method is more memory efficient and often faster for sorted arrays.

Understanding tradeoffs helps choose the best method for performance and memory in real systems.

Under the Hood

The two pointer method works by maintaining a slow pointer (i) that marks the position of the last unique element. The fast pointer (j) scans through the array. When a new unique element is found at j, it is copied to i+1, and i moves forward. This overwrites duplicates and compacts unique elements at the front. The array's sorted property guarantees duplicates are adjacent, so a single pass suffices.

Why designed this way?

This approach was designed to optimize space and time. Earlier methods used extra memory or multiple passes. The sorted array property allows a linear scan with two pointers to efficiently remove duplicates in place, minimizing memory use and improving speed.

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

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

Step 1: arr[j] == arr[i], j++
Step 2: arr[j] != arr[i], i++, arr[i] = arr[j]

Process continues until j reaches end.

Final:
[1, 2, 3, 4, _, _]
 i=3 (last unique index)

Myth Busters - 3 Common Misconceptions

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

Common Belief: Many think removing duplicates always needs extra memory like a new array or set.

Reality: The two pointer method removes duplicates in place using constant extra space.

Why it matters: Believing extra memory is needed may lead to inefficient solutions and unnecessary memory use.

Quick: Does this method work correctly on unsorted arrays? Commit yes or no.

Common Belief: Some believe the two pointer method works on any array regardless of order.

Reality: It only works correctly on sorted arrays because duplicates must be adjacent.

Why it matters: Using it on unsorted arrays can miss duplicates and produce wrong results.

Quick: Does the first pointer move every step or only when a unique element is found? Commit your answer.

Common Belief: People often think both pointers move together at every step.

Reality: The first pointer moves only when a new unique element is found to compact the array.

Why it matters: Moving the first pointer incorrectly can overwrite unique elements or leave duplicates.

Expert Zone

1

The algorithm preserves the relative order of unique elements, which is important in many applications.

2

If the array is very large, in-place modification reduces memory overhead and cache misses compared to extra space methods.

3

The method can be adapted to remove duplicates from sorted linked lists by similar pointer logic.

When NOT to use

Do not use this method if the array is unsorted; instead, use hash sets or sorting first. Also, if you need to keep the original array unchanged, create a copy before removing duplicates.

Production Patterns

In production, this method is used in database query optimizations, data cleaning pipelines, and real-time data streams where memory and speed are critical. It is often combined with other two pointer techniques for complex array manipulations.

Connections

Sliding Window Technique

Both use multiple pointers to scan arrays efficiently.

Understanding two pointers here helps grasp sliding windows, which also use pointers to track subarrays dynamically.

Linked List Deduplication

Similar pointer logic applies to removing duplicates from sorted linked lists.

Knowing array two pointers makes it easier to understand linked list pointer manipulations for deduplication.

Data Compression

Removing duplicates is a form of data reduction, related to compression techniques that remove redundancy.

Recognizing duplicate removal as a compression step helps appreciate its role in efficient data storage and transmission.

Common Pitfalls

#1 Moving the first pointer every step instead of only on unique elements.

Wrong approach:

for (int j = 1; j < nums.size(); j++) {
i++;
nums[i] = nums[j];
}

Correct approach:

for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}

Root cause:

Misunderstanding that the first pointer should only move when a new unique element is found.

#2 Not handling empty arrays, causing out-of-bounds errors.

Wrong approach:

int removeDuplicates(vector& nums) {
int i = 0;
for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}

Correct approach:

int removeDuplicates(vector& nums) {
if (nums.empty()) return 0;
int i = 0;
for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}

Root cause:

Forgetting to check for empty input before accessing elements.

#3 Using this method on unsorted arrays expecting correct results.

Wrong approach:

int removeDuplicates(vector& nums) {
int i = 0;
for (int j = 1; j < nums.size(); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
// nums = [3,1,2,3,1]

Correct approach:

// Sort first
sort(nums.begin(), nums.end());
// Then apply removeDuplicates as above

Root cause:

Assuming duplicates are adjacent without sorting first.

Key Takeaways

Removing duplicates from a sorted array can be done efficiently using two pointers in one pass.

The first pointer tracks the position of the last unique element, moving only when a new unique element is found.

This method modifies the array in place, saving memory and preserving the order of unique elements.

It only works correctly on sorted arrays because duplicates must be adjacent to detect them in one pass.

Handling edge cases like empty or single-element arrays is essential for robust code.

Practice

1. What is the main purpose of the two-pointer technique in removing duplicates from a sorted array?

easy

A. To track unique elements and overwrite duplicates in-place

B. To sort the array again after removing duplicates

C. To create a new array with duplicates removed

D. To count the total number of duplicates only

Solution

1. Step 1: Understand the two-pointer roles

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

2. Step 2: Overwrite duplicates in-place

   When a new unique element is found, it is placed at the tracked position, replacing duplicates.

3. Final Answer:

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

4. Quick Check:

   Two-pointer technique = overwrite duplicates [OK]

Hint: Two pointers: one scans, one writes unique values [OK]

Common Mistakes:

• Thinking it creates a new array instead of modifying in-place
• Assuming it sorts the array again
• Confusing counting duplicates with removing them

2. Which of the following is the correct syntax to initialize the two pointers for removing duplicates from a sorted array nums in C++?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0, j = 0;

D. int i = 1, j = 1;

Solution

1. Step 1: Identify pointer roles

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

2. Step 2: Initialize pointers accordingly

   Set i = 0 and j = 1 to start comparing from the second element.

3. Final Answer:

   int i = 0, j = 1; -> Option A

4. Quick Check:

   i=0, j=1 start positions [OK]

Hint: Start i at 0, j at 1 to compare neighbors [OK]

Common Mistakes:

• Starting both pointers at 0
• Swapping i and j initialization
• Starting j before i

3. What will be the output length after removing duplicates using the two-pointer method on the sorted array nums = {1, 1, 2, 3, 3, 4}?

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 1, 2, 3, 4.

2. Step 2: Count unique elements

   There are 4 unique elements, so the length after removal is 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Unique count = 4 [OK]

Hint: Count unique numbers in sorted array [OK]

Common Mistakes:

• Counting duplicates as unique
• Confusing length with original array size
• Off-by-one errors in counting

4. Identify the error in the following C++ code snippet for removing duplicates from a sorted array nums:

int removeDuplicates(vector<int>& nums) {
    int i = 0, j = 1;
    while (j < nums.size()) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. The loop should use for instead of while

B. Pointers i and j should start at 1 and 0 respectively

C. The condition should be nums[i] == nums[j] instead of !=

D. Return value should be i + 1, not i

Solution

1. Step 1: Understand pointer i meaning

   Pointer i is index of last unique element, so length is i + 1.

2. Step 2: Check return statement

   Returning i alone gives index, not count; must return i + 1 for length.

3. Final Answer:

   Return value should be i + 1, not i -> Option D

4. Quick Check:

   Length = last index + 1 [OK]

Hint: Return i + 1 as length, not i [OK]

Common Mistakes:

• Returning i instead of i + 1
• Swapping pointer initializations
• Using wrong comparison operator

5. Given a sorted array nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}, what will be the state of the array after applying the two-pointer method to remove duplicates, and what is the new length?

hard

A. Array: {0, 1, 1, 2, 3, 4, _, _, _, _}, Length: 4

B. Array: {0, 0, 1, 1, 2, 2, 3, 3, 4, 4}, Length: 6

C. Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5

D. Array: {0, 1, 2, 3, 4, 5, _, _, _, _}, Length: 6

Solution

1. Step 1: Identify unique elements in order

   Unique elements are 0, 1, 2, 3, 4.

2. Step 2: Overwrite duplicates in-place

   Using two pointers, these unique elements overwrite the start of the array.

3. Step 3: Determine new length

   There are 5 unique elements, so length is 5.

4. Final Answer:

   Array: {0, 1, 2, 3, 4, _, _, _, _, _}, Length: 5 -> Option C

5. Quick Check:

   Unique elements = 5, array start updated [OK]

Hint: Unique elements overwrite start, length = count unique [OK]

Common Mistakes:

• Not overwriting duplicates correctly
• Miscounting unique elements
• Assuming array length stays same