Remove Duplicates from Sorted Array Two Pointer in DSA C

Mental Model

Use two pointers to keep track of unique elements and overwrite duplicates in place.

Analogy: Imagine sorting your bookshelf and moving only unique books forward, skipping duplicates as you go.

[1, 1, 2, 2, 3, 3, 4]
 ↑  ↑
left right

Dry Run Walkthrough

Input: array: [1, 1, 2, 2, 3], remove duplicates in place

Goal: Keep only unique elements at the start of the array and find the new length

Step 1: Initialize left at index 0, right at index 1

[1, 1, 2, 2, 3]
 ↑  ↑
left right

Why: Left points to last unique element, right scans for new unique

Step 2: Compare array[right] with array[left], both 1, duplicate found, move right forward

[1, 1, 2, 2, 3]
 ↑     ↑
left   right

Why: Skip duplicate by moving right pointer

Step 3: array[right] = 2 differs from array[left] = 1, increment left and copy 2 to left

[1, 2, 2, 2, 3]
    ↑  ↑
   left right

Why: Found new unique, move left forward and overwrite

Step 4: Compare array[right] = 2 with array[left] = 2, duplicate, move right forward

[1, 2, 2, 2, 3]
    ↑     ↑
   left   right

Why: Skip duplicate by moving right pointer

Step 5: array[right] = 3 differs from array[left] = 2, increment left and copy 3

[1, 2, 3, 2, 3]
       ↑  ↑
      left right

Why: Found new unique, move left forward and overwrite

Step 6: Right pointer reached end, stop

[1, 2, 3, 2, 3]
       ↑
      left

Why: All unique elements processed

Result:

[1, 2, 3, 2, 3]
Unique length = 3

Annotated Code

DSA C

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int left = 0;
    for (int right = 1; right < numsSize; right++) {
        if (nums[right] != nums[left]) {
            left++;
            nums[left] = nums[right];
        }
    }
    return left + 1;
}

int main() {
    int nums[] = {1, 1, 2, 2, 3};
    int size = sizeof(nums) / sizeof(nums[0]);
    int newLength = removeDuplicates(nums, size);
    for (int i = 0; i < newLength; i++) {
        printf("%d", nums[i]);
        if (i < newLength - 1) printf(" -> ");
    }
    printf(" -> null\n");
    printf("Unique length = %d\n", newLength);
    return 0;
}

if (numsSize == 0) return 0;

handle empty array edge case

int left = 0;

initialize left pointer to track last unique element

for (int right = 1; right < numsSize; right++) {

right pointer scans through array

if (nums[right] != nums[left]) {

check if current element is new unique

left++;

move left pointer forward to next unique position

nums[left] = nums[right];

overwrite duplicate with new unique element

return left + 1;

return count of unique elements

Output

1 -> 2 -> 3 -> null

Unique length = 3

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: Naive approach uses extra space to store unique elements, increasing space to O(n)

Edge Cases

empty array

returns 0 immediately, no processing

DSA C

if (numsSize == 0) return 0;

array with all duplicates

returns 1, only one unique element kept

DSA C

if (nums[right] != nums[left]) {

array with no duplicates

returns original length, array unchanged

DSA C

if (nums[right] != nums[left]) {

When to Use This Pattern

When you see a sorted array and need to remove duplicates in place, use two pointers to overwrite duplicates efficiently.

Common Mistakes

Mistake: Starting left pointer at -1 or forgetting to initialize it properly
Fix: Initialize left pointer at 0 to track the first unique element

Mistake: Copying elements even when they are duplicates
Fix: Only copy when nums[right] != nums[left]

Mistake: Returning left instead of left + 1 as the new length
Fix: Return left + 1 because left is index-based

Summary

Removes duplicates from a sorted array by overwriting duplicates in place.

Use when you want to keep only unique elements without extra space.

Two pointers track unique elements and overwrite duplicates efficiently.

Practice

1. What is the main purpose of using two pointers in the Remove Duplicates from Sorted Array problem?

easy

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

B. To sort the array before removing duplicates

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 A

4. Quick Check:

   Two pointers help remove duplicates in-place [OK]

Hint: Two pointers track unique and current elements [OK]

Common Mistakes:

• Thinking two pointers sort the array
• Assuming a new array is created
• Confusing counting duplicates with removing them

2. Which of the following is the correct syntax to initialize two pointers i and j for the two-pointer approach in C?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

C. int i = 0; int j = 0;

D. int i, j = 0;

Solution

1. Step 1: Understand pointer roles

   Pointer i starts at 0 (first unique), j starts at 1 (scanning next elements).

2. Step 2: Correct initialization syntax

   Both pointers must be initialized properly; int i = 0, j = 1; is correct in C.

3. Final Answer:

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

4. Quick Check:

   Initialize i=0 and j=1 for two-pointer [OK]

Hint: Start i at 0 and j at 1 for scanning [OK]

Common Mistakes:

• Swapping initial values of i and j
• Initializing both pointers to 0
• Incorrect declaration syntax

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

medium

A. 6

B. 5

C. 3

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1. Compare elements: duplicates skipped, unique elements moved forward.

2. Step 2: Count unique elements

   Unique elements are 1, 2, 3, 4. So length is 4 after removal.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Unique elements count = 4 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates as unique
• Assuming length stays same
• Miscounting unique elements

4. Identify the bug in this C code snippet for removing duplicates from a sorted array:

int removeDuplicates(int* nums, int numsSize) {
    int i = 0, j = 1;
    while (j < numsSize) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }
    return i;
}

medium

A. Does not check for array size zero

B. Pointers i and j are initialized incorrectly

C. Returns i instead of i+1 as new length

D. Uses while loop instead of for loop

Solution

1. Step 1: Analyze return value

   Variable i tracks last unique index, so length is i+1, not i.

2. Step 2: Identify correct return

   Returning i misses counting the first element, causing off-by-one error.

3. Final Answer:

   Returns i instead of i+1 as new length -> Option C

4. Quick Check:

   Return length = i+1, not i [OK]

Hint: Return last index + 1 for length [OK]

Common Mistakes:

• Off-by-one error in return value
• Ignoring empty array edge case
• Confusing pointer initialization

5. Given a sorted array nums = [0,0,1,1,1,2,2,3,3,4], what will be the array state after applying the two-pointer method to remove duplicates?

hard

A. [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]

B. [0, 1, 2, 3, 4, _, _, _, _, _]

C. [0, 1, 1, 2, 3, 4, _, _, _, _]

D. [0, 1, 2, 3, 4, 5, _, _, _, _]

Solution

1. Step 1: Apply two-pointer overwrite

   Unique elements 0,1,2,3,4 are moved to front positions in array.

2. Step 2: Final array state

   Positions after unique elements remain unchanged or ignored (represented as underscores).

3. Final Answer:

   [0, 1, 2, 3, 4, _, _, _, _, _] -> Option B

4. Quick Check:

   Array front holds unique elements [OK]

Hint: Unique elements overwrite front, rest ignored [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Confusing array length with content