Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place so that each unique element appears only once. The relative order must stay the same.

Let k be the number of unique elements. Return k.

The first k elements of nums must hold the unique values in sorted order. Whatever is beyond index k - 1 can be ignored.

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

Brute Force

Put every value into an ordered set. A set keeps only one copy of each value, so the duplicates disappear.

1. Walk through nums and insert every value into the set.
2. Walk through the set from smallest to largest.
3. Write each value into nums, starting at index 0.
4. Return the number of values written. That is k.

This works, but it ignores that the array is already sorted. An ordered set has to keep its values in order, which costs extra time, and it also needs extra memory.

class Solution {
    public:
    int removeDuplicates(vector<int>& nums) {
        set<int> uniqueValues;

        for (int value : nums) {
            uniqueValues.insert(value);
        }

        int index = 0;

        for (int value : uniqueValues) {
            nums[index] = value;
            index++;
        }

        return index;
    }
};

• Time: O(n log n). Inserting into an ordered set costs O(log n) per value.
• Space: O(n). The set can hold every value.

Optimal Approach: Two Pointers

The array is sorted, so all copies of a value sit next to each other. That means we do not need a set. We only need to compare neighbors.

We use two pointers:

• lastUnique: the index of the last unique value we have kept. It starts at 0, because the first value is always unique.
• readIndex: the index we are reading now. It starts at 1.

Steps:

1. Set lastUnique = 0.
2. Loop readIndex from 1 to the end.
3. If nums[readIndex] is different from nums[lastUnique], we found a new unique value:
   • Move lastUnique forward by one.
   • Copy nums[readIndex] into nums[lastUnique].
4. If it is the same, skip it.
5. Return lastUnique + 1, because indexes start at 0.

class Solution {
    public:
    int removeDuplicates(vector<int>& nums) {
        int lastUnique = 0;

        for (int readIndex = 1; readIndex < nums.size(); readIndex++) {
            if (nums[readIndex] != nums[lastUnique]) {
                lastUnique++;
                nums[lastUnique] = nums[readIndex];
            }
        }

        return lastUnique + 1;
    }
};

Complexity

How to Explain It in an Interview