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. Initialization: Initialize a pointer k to 1. This pointer will track the index where the next unique element should be placed. We start at index 1 because nums[0] is always unique (unless the array is empty).

2. Iteration: Iterate through the array starting from the second element (i = 1).

3. Comparison: Compare the current element nums[i] with the previous unique element nums[k-1].

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

5. Duplicate Element: If nums[i] is the same as nums[k-1], it's a duplicate. Skip it.

6. Return: After iterating through the entire array, k will represent the new length of the array containing only unique elements. Return k.

Explanation:

The algorithm uses a two-pointer approach. One pointer (i) iterates through the entire array, and the other pointer (k) tracks the index of the next unique element. By only copying unique elements to the beginning of the array, we effectively remove duplicates in-place. The elements beyond the kth index are not relevant to the problem's solution.

Code:

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 0) return 0; //Handle empty array case

        int k = 1; // Pointer for the next unique element
        for (int 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 array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space. The modification is done in-place.