Remove Duplicates from Sorted Array

How it works

A more elegant approach: we compare each element with its predecessor. Since duplicates are consecutive in a sorted array, an element is unique if it differs from the one before it. We maintain a write pointer that only advances when we find a new unique value.

Steps

1. Start with l = 1 since the first element is always unique.
2. Iterate r from 1 to the end of the array.
3. If nums[r] differs from nums[r - 1], it's a new unique value.
4. Copy it to position l and increment l.
5. Return l as the count of unique elements.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Not Leveraging the Sorted Property

The array is already sorted, meaning duplicates are always adjacent. Some solutions use a hash set or sort the array again, which wastes time and space. Since duplicates are consecutive, you only need to compare each element with its predecessor (or the last written element) to detect duplicates in O(1) space.

Returning the Wrong Value

The function should return the count of unique elements, not modify and return the array itself. Additionally, the returned length k means the first k elements of nums contain the unique values. Some solutions off-by-one error by returning l - 1 instead of l, or forget that the write pointer already represents the count of unique elements written.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        l = 1
        for r in range(1, len(nums)):
            if nums[r] != nums[r - 1]:
                nums[l] = nums[r]
                l += 1
        return l

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 1;
        for (int r = 1; r < nums.size(); r++) {
            if (nums[r] != nums[r - 1]) {
                nums[l++] = nums[r];
            }
        }
        return l;
    }
};