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 a pointer: Create a pointer k to track the index of the next unique element. Start k at 1 (the second element).

2. Iterate through the array: Iterate through the array starting from the second element (index 1).

3. Compare with the previous element: Compare each element nums[i] with the element at index k-1 (the previously stored unique element).

4. If different, update: If nums[i] is different from nums[k-1], it's a unique element. Increment k and copy nums[i] to nums[k].

5. Return the length: After iterating through the entire array, k will represent the index one past the last unique element. Therefore, return k.

Explanation

The algorithm uses a two-pointer approach. One pointer (i) iterates through the entire array, while another pointer (k) keeps track of the index where the next unique element should be placed. The algorithm only copies an element to the kth position if it's different from the element at k-1, effectively removing duplicates in place. The space complexity is O(1) because we are modifying the array in-place, and the time complexity is O(n) because we iterate through the array once.

Code

function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0; //Handle empty array case

    let k = 1; // Pointer for the next unique element

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

    return k;
};

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We are modifying the array in-place; no extra space is used.