Remove Duplicates from Sorted Array Two Pointer in DSA Java

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, 3, 3, 4, 5]
 ↑   ↑
left right

Dry Run Walkthrough

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

Goal: Remove duplicates so each element appears once, modifying array in place

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

[1, 1, 2, 3, 3, 4, 5]
 ↑   ↑

Why: Left tracks last unique element, right scans for new unique elements

Step 2: Compare elements at left and right; both are 1, duplicate found, move right forward

[1, 1, 2, 3, 3, 4, 5]
 ↑       ↑

Why: Skip duplicate by moving right pointer

Step 3: Elements differ (1 vs 2), increment left and copy right element to left

[1, 2, 2, 3, 3, 4, 5]
    ↑    ↑

Why: Place new unique element next to last unique

Step 4: Move right forward to index 3, compare with left element (2 vs 3), different

[1, 2, 2, 3, 3, 4, 5]
       ↑ ↑

Why: Found next unique element

Step 5: Increment left and copy right element to left

[1, 2, 3, 3, 3, 4, 5]
          ↑ ↑

Why: Keep unique elements compacted at front

Step 6: Right moves to index 4, element 3 equals left element 3, duplicate, move right forward

[1, 2, 3, 3, 3, 4, 5]
          ↑    ↑

Why: Skip duplicate

Step 7: Right at index 5, element 4 differs from left element 3, increment left and copy

[1, 2, 3, 4, 3, 4, 5]
             ↑    ↑

Why: Add new unique element

Step 8: Right at index 6, element 5 differs from left element 4, increment left and copy

[1, 2, 3, 4, 5, 4, 5]
                ↑    ↑

Why: Add last unique element

Result:

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

Annotated Code

DSA Java

public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int left = 0;
        for (int right = 1; right < nums.length; right++) {
            if (nums[right] != nums[left]) {
                left++;
                nums[left] = nums[right];
            }
        }
        return left + 1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 3, 4, 5};
        int length = removeDuplicates(nums);
        for (int i = 0; i < length; i++) {
            System.out.print(nums[i]);
            if (i < length - 1) System.out.print(" -> ");
        }
        System.out.println(" -> null");
        System.out.println("Unique length = " + length);
    }
}

if (nums.length == 0) return 0;

handle empty array edge case

int left = 0;

initialize left pointer to track last unique element

for (int right = 1; right < nums.length; right++) {

right pointer scans through array to find unique elements

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

check if current right element is new unique

left++;

move left pointer forward to place new unique

nums[left] = nums[right];

overwrite duplicate with new unique element

return left + 1;

return count of unique elements

Output

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

Unique length = 5

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 needed

DSA Java

if (nums.length == 0) return 0;

array with all duplicates

returns 1, only one unique element kept

DSA Java

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

array with no duplicates

returns full length, array unchanged

DSA Java

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 first unique element

Mistake: Copying elements even when they are duplicates
Fix: Only copy when right element differs from left element

Mistake: Returning left instead of left + 1 as length
Fix: Return left + 1 because left is index of last unique

Summary

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

Use when you want to keep only unique elements in a sorted array without extra space.

The key insight is using two pointers: one to track unique elements and one to scan for new ones.

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 count the total number of duplicates in the array

C. To create a new array with unique elements

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

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, keeping unique elements at the start.

3. Final Answer:

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

4. Quick Check:

   Two pointers help remove duplicates without extra space [OK]

Hint: Two pointers move to keep unique elements compact [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 the two pointers i and j for the problem in Java?

easy

A. int i = 0, j = 1;

B. int i = 1, j = 0;

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

D. int i = 1; int j = 1;

Solution

1. Step 1: Identify pointer roles

   Pointer i starts at 0 to track unique elements, j starts at 1 to scan ahead.

2. Step 2: Check initialization correctness

   Initializing i = 0 and j = 1 allows scanning from second element while i marks last unique.

3. Final Answer:

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

4. Quick Check:

   Start i at 0, j at 1 to scan array [OK]

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

Common Mistakes:

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

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

medium

A. 2

B. 3

C. 5

D. 4

Solution

1. Step 1: Trace the two-pointer process

   Start with i=0, j=1; compare elements and overwrite duplicates: unique elements are 1, 2, 3.

2. Step 2: Count unique elements

   After processing, unique elements count is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Unique elements count = 3 [OK]

Hint: Count unique elements after skipping duplicates [OK]

Common Mistakes:

• Counting duplicates instead of unique
• Assuming length stays same
• Miscounting when duplicates are consecutive

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

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

medium

A. Pointers initialized incorrectly

B. Incorrect comparison operator used

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

D. Does not increment j inside the loop

Solution

1. Step 1: Analyze return value

   The variable i tracks last unique index, so length is i + 1.

2. Step 2: Identify mistake in return

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

3. Final Answer:

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

4. Quick Check:

   Length = last index + 1 [OK]

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

Common Mistakes:

• Returning i instead of i + 1
• Forgetting to increment j
• Using wrong comparison operator

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, 1, 2, 3, 4, _, _, _, _, _]

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

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

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

Solution

1. Step 1: Apply two-pointer overwrite

   Start with i=0, j=1; overwrite duplicates by moving unique elements forward: unique elements are 0,1,2,3,4.

2. Step 2: Final array state

   First five positions hold unique elements [0,1,2,3,4], rest remain unchanged or ignored.

3. Final Answer:

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

4. Quick Check:

   Unique elements compacted at start [OK]

Hint: Unique elements fill front, duplicates ignored after [OK]

Common Mistakes:

• Assuming duplicates remain in place
• Misplacing unique elements
• Counting extra elements beyond unique count