Remove Duplicates from Sorted Array easy

Problem Statement

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. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

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 length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Steps:

1. Initialize two pointers: slow and fast. slow points to the position where the next unique element will be placed, and fast iterates through the array. Initially, both slow and fast point to the beginning of the array (index 0).

2. Iterate: The fast pointer traverses the array.

3. Compare: If nums[slow] is different from nums[fast], it means we've encountered a new unique element.

4. Increment and copy: Increment slow and copy the value at nums[fast] to nums[slow].

5. Continue: The loop continues until fast reaches the end of the array.

6. Return: The value of slow + 1 represents the new length of the array containing only unique elements.

Explanation

The algorithm leverages the fact that the input array is sorted. Because it's sorted, duplicate elements will be adjacent to each other. The slow pointer keeps track of the index where the next unique element should be placed. The fast pointer iterates through the array, finding unique elements. When a unique element is found, it's copied to the position indicated by slow, and slow is incremented. This effectively overwrites the duplicate elements with unique ones.

Code

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

        int slow = 0;
        for (int fast = 1; fast < nums.size(); ++fast) {
            if (nums[slow] != nums[fast]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. The algorithm iterates through the array once.
• Space Complexity: O(1). The algorithm modifies the input array in-place and uses only a constant amount of extra space for the slow and fast pointers.