26_Remove Duplicates from Sorted Array

28. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return 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:

Given nums = [1,1,2],

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 new length.

Solution 1

If we really want to delete those duplicated elements:

def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i = 1
    while i < len(nums):
        if nums[i] == nums[i-1]:
            nums.pop(i)
        else:
            i += 1
    return len(nums)

Solution 2

If we can just put those non-duplicated elements at the begining of the array:

Need two pointers. Use fast pointer to loop from left to right. Use slow pointer to record the first place that have duplicates.

Time complexity: $O(n)$

Space complexity: $O(1)$

def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """ 

    # corner case
    if len(nums) == 0:
        return 0

    # write_index is the position for next write (slow pointer)
    # write_index-1 is the position for latest value
    write_index = 1

    # i is the faster pointer
    for i in range(1, len(nums)):
        if nums[write_index - 1] != nums[i] :
            nums[write_index] = nums[i]
            write_index += 1
    return write_index

Variant

• Leetcode 27

• Leetcode 80