Remove Duplicates from Sorted Array

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 must remain unchanged. Return the number of unique elements in nums.

Let $k$ be the number of unique elements in nums. To be accepted, the solution must:

1. Modify nums so that the first $k$ elements contain the unique elements in their original order
2. Return $k$ (the remaining elements of nums are irrelevant)

This problem demonstrates the two-pointer technique, similar to Move Zeroes, where one pointer tracks the position for the next unique element while another scans through the array.

Custom Judge

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
 
int k = removeDuplicates(nums); // Calls your implementation
 
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Solution

#include <vector>
using namespace std;
 
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // If the array has 0 or 1 element, there are no duplicates to remove.
        // The number of unique elements is simply the size of the array.
        if (nums.size() <= 1) {
            return nums.size();
        }
 
        // 'i' is the "unique" pointer. It points to the last known unique element.
        // It starts at index 0, as the first element is always unique.
        int i = 0;
 
        // 'j' is the "iterator" pointer. It scans the entire array starting from the second element.
        for (int j = 1; j < nums.size(); ++j) {
            // Compare the element at 'j' with the element at 'i'.
            // Since the array is sorted, duplicates are adjacent.
            // If the element at 'j' is different from the one at 'i', it means we've found a new unique element.
            if (nums[j] != nums[i]) {
                // First, advance the 'i' pointer. This moves it to the next available position
                // for a unique number.
                i++;
                // Then, copy the unique element from 'j' to the new position 'i'.
                // This overwrites the duplicate that was previously at index 'i'.
                nums[i] = nums[j];
            }
            // If nums[j] == nums[i], it's a duplicate. We simply do nothing and let the 'j' pointer advance.
            // This effectively skips the duplicate.
        }
 
        // The number of unique elements is 'i + 1' because 'i' is a 0-indexed position.
        // The function is expected to return the new length of the array.
        return i + 1;
    }
};