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: We'll use a pointer k to keep track of the index where the next unique element should be placed. Initialize k to 1 (because the first element is always unique).

2. Iterate through the array: Starting from the second element (index 1), compare each element with the element at index k-1.

3. Check for duplicates: If the current element is different from the element at k-1, it's a unique element.

4. Update the array and pointer: Copy the current element to the index k and increment k.

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

Explanation

The algorithm leverages the fact that the input array is sorted. This allows us to efficiently identify duplicates by simply comparing each element to its predecessor. We overwrite duplicate elements with unique elements, effectively shrinking the array in-place. The k pointer acts as a "write head," always pointing to the next available slot for a unique element.

Code

def removeDuplicates(nums):
    """
    Removes duplicates from a sorted array in-place.

    Args:
        nums: A sorted list of integers.

    Returns:
        The new length of the array after removing duplicates.
    """
    if not nums:  # Handle empty array case
        return 0

    k = 1  # Pointer to the next unique element's position
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    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 use only a constant amount of extra space. The modification happens in-place.