Remove Duplicates from Sorted Array

Source: Dev.to

Problem Statement

Given a sorted integer array nums, remove the duplicates in-place such that each unique element appears only once.

Return the number of unique elements k.

The first k elements of the array should contain the unique elements in their original order.

Example

Input:

nums = [1,1,2]

Enter fullscreen mode


Exit fullscreen mode

Output:

2

Enter fullscreen mode


Exit fullscreen mode

Modified Array:

[1,2,_]

Enter fullscreen mode


Exit fullscreen mode

Brute Force Intuition (Interview Explanation)

One straightforward approach is to use a separate data structure like a HashSet to store unique elements.

As we traverse the array, we insert elements into the set and then copy them back into the original array.

Although simple, it violates the in-place requirement and uses extra memory.

Time Complexity

O(N)

Enter fullscreen mode


Exit fullscreen mode

Space Complexity

O(N)

Enter fullscreen mode


Exit fullscreen mode

Brute Force Java

class Solution {
    public int removeDuplicates(int[] nums) {

        HashSet set = new HashSet<>();

        for (int num : nums) {
            set.add(num);
        }

        int index = 0;

        for (int num : set) {
            nums[index++] = num;
        }

        return set.size();
    }
}

Enter fullscreen mode


Exit fullscreen mode

Moving Towards Optimal

Since the array is already sorted, all duplicate values will appear together.

This means we do not need a HashSet.

We can maintain one pointer for the position of the last unique element and another pointer to explore the array.

Whenever we find a new unique value, we place it next to the previous unique value.

This gives an in-place solution with constant extra space.

Optimal Approach – Two Pointers

Algorithm

• Keep pointer i at the last unique element.

• Traverse the array using pointer j.

If nums[j] is different from nums[i]:

• Move i forward.

• Place nums[j] at index i.

• At the end, unique elements occupy positions 0 to i.

• Return i + 1.

  Why Two Pointers Work

Because the array is sorted:

1 1 1 2 2 3 4 4

Enter fullscreen mode


Exit fullscreen mode

All duplicates are adjacent.

So comparing the current element with the last unique element is enough to detect duplicates.

Optimal Java Solution

class Solution {
    public int removeDuplicates(int[] nums) {

        int i = 0;

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

            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }

        return i + 1;
    }
}

Enter fullscreen mode


Exit fullscreen mode

Dry Run

Input:

nums = [1,1,2,2,3,4,4]

Enter fullscreen mode


Exit fullscreen mode

Initial:

i = 0
j = 1

Enter fullscreen mode


Exit fullscreen mode

Step 1

nums[j] = 1
nums[i] = 1

Duplicate found

Enter fullscreen mode


Exit fullscreen mode

i = 0

Enter fullscreen mode


Exit fullscreen mode

Step 2

nums[j] = 2
nums[i] = 1

Unique element found

Enter fullscreen mode


Exit fullscreen mode

i = 1
nums[1] = 2

Enter fullscreen mode


Exit fullscreen mode

Array:

[1,2,2,2,3,4,4]

Enter fullscreen mode


Exit fullscreen mode

Step 3

nums[j] = 2
nums[i] = 2

Duplicate

Enter fullscreen mode


Exit fullscreen mode

Step 4

nums[j] = 3
nums[i] = 2

Unique

Enter fullscreen mode


Exit fullscreen mode

i = 2
nums[2] = 3

Enter fullscreen mode


Exit fullscreen mode

Array:

[1,2,3,2,3,4,4]

Enter fullscreen mode


Exit fullscreen mode

Step 5

nums[j] = 4
nums[i] = 3

Unique

Enter fullscreen mode


Exit fullscreen mode

i = 3
nums[3] = 4

Enter fullscreen mode


Exit fullscreen mode

Final Array:

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

Enter fullscreen mode


Exit fullscreen mode

Return:

i + 1 = 4

Enter fullscreen mode


Exit fullscreen mode

Pattern Recognition

This pattern is commonly used when:

• Array is sorted

• Duplicates need to be removed in-place

• Stable ordering must be preserved

• Constant extra space is required

Keywords that should trigger this pattern:

Sorted Array
In-place Modification
Remove Duplicates
Unique Elements

Enter fullscreen mode


Exit fullscreen mode

Think:

Two Pointers
Slow Pointer = Last Valid Position
Fast Pointer = Explorer

Enter fullscreen mode


Exit fullscreen mode

Interview One-Liner

Since the array is sorted, duplicates appear consecutively. Using a slow pointer to track the last unique element and a fast pointer to scan the array allows us to overwrite duplicates in-place, achieving O(N) time and O(1) space.