Remove Duplicates from Sorted Array

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]

Output:

2

Modified Array:

[1,2,_]

---

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)

Space Complexity

O(N)

Brute Force Java

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

        HashSet<Integer> set = new HashSet<>();

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

        int index = 0;

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

        return set.size();
    }
}

---

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

1. Keep pointer i at the last unique element.
2. Traverse the array using pointer j.
3. If nums[j] is different from nums[i]:
   • Move i forward.
   • Place nums[j] at index i.
4. At the end, unique elements occupy positions 0 to i.
5. Return i + 1.

Why Two Pointers Work

Because the array is sorted:

1 1 1 2 2 3 4 4

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;
    }
}

---

Dry Run

Input:

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

Initial:

i = 0
j = 1

Step 1

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

Duplicate found

i = 0

Step 2

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

Unique element found

i = 1
nums[1] = 2

Array:

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

Step 3

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

Duplicate

Step 4

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

Unique

i = 2
nums[2] = 3

Array:

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

Step 5

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

Unique

i = 3
nums[3] = 4

Final Array:

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

Return:

i + 1 = 4

---

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

Think:

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

---

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.