Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array. Modify the input array in-place with O(1) extra memory.

Sample Input and Expected Output:

Input:

nums = [1, 1, 2]

Output:

Length after removing duplicates: 2 // The array becomes [1, 2]

Input:

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

Output:

Length after removing duplicates: 5 // The array becomes [0, 1, 2, 3, 4]

Solution in C++:

The idea is to use a two-pointer approach. We use one pointer (i) to iterate through the array and another pointer (j) to keep track of the position where we need to insert the next unique element. As the array is sorted, duplicate elements will be adjacent to each other. So, whenever we find a different element, we place it at the position pointed by j and increment both i and j. The final value of j will give us the new length of the array without duplicates.

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) {
        return 0; // If the array is empty, no duplicates to remove.
    }

    int j = 0; // Pointer to track the position to insert unique elements.

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[j]) {
            j++; // Move j to the next position.
            nums[j] = nums[i]; // Place the unique element at the new position.
        }
    }

    return j + 1; // Length of the array without duplicates.
}

int main() {
    std::vector<int> nums1 = {1, 1, 2};
    std::vector<int> nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};

    int length1 = removeDuplicates(nums1);
    int length2 = removeDuplicates(nums2);

    std::cout << "Length after removing duplicates: " << length1 << std::endl;
    std::cout << "Length after removing duplicates: " << length2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. This is because we use a two-pointer approach that traverses the array once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The removal of duplicates is performed in-place, modifying the original array.