Remove Duplicates from Sorted Array Two Pointer in DSA C++

Mental Model

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

Analogy: Imagine sorting your bookshelf and removing duplicate books by sliding unique books forward to fill gaps left by duplicates.

Array: [1, 1, 2, 2, 3, 4, 4]
Pointers: i ↑ j ↑
Initially both at start, i marks last unique, j scans ahead

Dry Run Walkthrough

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

Goal: Remove duplicates in-place so that the first part of the array contains only unique elements

Step 1: Start with i=0 (first unique), j=1 scanning next element

[1 (i), 1 (j), 2, 2, 3, 4, 4]

Why: We compare j with i to find new unique elements

Step 2: j=1 equals i=0 value (1), so skip duplicate, move j forward

[1 (i), 1, 2 (j), 2, 3, 4, 4]

Why: Duplicate found, no change to i, just advance j

Step 3: j=2 value (2) differs from i=0 value (1), increment i and copy 2 to i

[1, 2 (i), 2 (j), 2, 3, 4, 4]

Why: Found new unique, move i forward and overwrite

Step 4: j=3 value (2) equals i=1 value (2), skip duplicate, move j forward

[1, 2 (i), 2, 2 (j), 3, 4, 4]

Why: Duplicate found, no change to i

Step 5: j=4 value (3) differs from i=1 value (2), increment i and copy 3 to i

[1, 2, 3 (i), 2, 3 (j), 4, 4]

Why: New unique found, move i forward and overwrite

Step 6: j=5 value (4) differs from i=2 value (3), increment i and copy 4 to i

[1, 2, 3, 4 (i), 3, 4 (j), 4]

Why: New unique found, move i forward and overwrite

Step 7: j=6 value (4) equals i=3 value (4), skip duplicate, move j forward

[1, 2, 3, 4 (i), 3, 4, 4 (j)]

Why: Duplicate found, no change to i

Result:

Final array front: [1, 2, 3, 4] with length 4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int i = 0; // last unique element index
    for (int j = 1; j < (int)nums.size(); j++) {
        if (nums[j] != nums[i]) {
            i++; // move i forward
            nums[i] = nums[j]; // overwrite duplicate
        }
    }
    return i + 1; // length of unique elements
}

int main() {
    vector<int> nums = {1, 1, 2, 2, 3, 4, 4};
    int length = removeDuplicates(nums);
    for (int k = 0; k < length; k++) {
        cout << nums[k];
        if (k < length - 1) cout << " -> ";
    }
    cout << " -> null" << endl;
    return 0;
}

if (nums.empty()) return 0;

handle empty array edge case

int i = 0; // last unique element index

initialize pointer i to track last unique element

for (int j = 1; j < (int)nums.size(); j++) {

j scans through array from second element

if (nums[j] != nums[i]) {

check if current j element is new unique

i++;

advance i to next position for unique element

nums[i] = nums[j];

overwrite duplicate with new unique element

return i + 1;

return count of unique elements

Output

1 -> 2 -> 3 -> 4 -> null

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 space

vs Alternative: Compared to creating a new array for unique elements (O(n) space), this uses constant space and is more efficient

Edge Cases

empty array

returns length 0 without error

DSA C++

if (nums.empty()) return 0;

array with all duplicates

returns length 1 with single unique element

DSA C++

if (nums[j] != nums[i]) {

array with no duplicates

returns original length, array unchanged

DSA C++

if (nums[j] != nums[i]) {

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: Starting both pointers at the same index and overwriting incorrectly
Fix: Start i at 0 and j at 1 so j scans ahead to find new unique elements

Mistake: Not returning the correct length of unique elements
Fix: Return i + 1 because i is zero-based index of last unique

Summary

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

Use when you need to remove duplicates in-place without extra space.

The key insight is to keep one pointer for the last unique element and another to scan ahead for new unique values.

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