Remove Duplicates from Sorted Array

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Examples

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Approach: Two Pointers

Explanation

We can solve this problem efficiently using two pointers:

Initialize two pointers: k at index 1 (since the first element is always unique) and i to iterate through the array starting from index 1.
Iterate through the array with i.
If the current element is different from the previous element, it's a new unique element. Copy it to the position k and increment k.
After the iteration, k will be the number of unique elements.

Time Complexity: O(n)

Space Complexity: O(1)

Implementation

Java Solution

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int k = 1; // pointer for the position of the last unique element

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}

C++ Solution

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int k = 1; // pointer for the position of the last unique element

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i-1]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
};

Explanation with Example

Let's walk through the solution using Example 2:

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

Initialize k = 1 (first element is always unique) and start iterating with i = 1.
nums[1] = 0 == nums[0], so we skip it: k remains 1
nums[2] = 1 != nums[1], so we keep it: nums[1] = 1, k = 2
nums[3] = 1 == nums[2], so we skip it: k remains 2
nums[4] = 1 == nums[3], so we skip it: k remains 2
nums[5] = 2 != nums[4], so we keep it: nums[2] = 2, k = 3
nums[6] = 2 == nums[5], so we skip it: k remains 3
nums[7] = 3 != nums[6], so we keep it: nums[3] = 3, k = 4
nums[8] = 3 == nums[7], so we skip it: k remains 4
nums[9] = 4 != nums[8], so we keep it: nums[4] = 4, k = 5

After the iteration, k = 5, and the first 5 elements of nums are [0,1,2,3,4].

This approach is efficient because:

It only requires a single pass through the array (O(n) time complexity).
It doesn't use any extra space (O(1) space complexity).
It modifies the array in-place, satisfying the problem requirement.
It maintains the relative order of the elements, as required by the problem.

The algorithm works correctly because the array is already sorted, so all duplicates of a number will be adjacent to each other.

Remove Element

Remove Duplicates from Sorted Array II