Remove Duplicates from Sorted Array

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.

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]

Approach1:

Since our array is sorted, we're able to arrive to a O(1) time solution or circumvent using extra space. We will use a Two-Pointer Technique by having i and j, each going at different speed and advancing under a certain condition.

• Pointer i and j both start at 0 with j moving forward by 1 at each iteration.

• When j encounters a different element (Since array is sorted, j just encountered the next element), move i forward by 1, then overwrite the element that i is now pointing to after advancing with the element that j is currently pointing to.

• We do this until j reaches the end of the array.

• We then return i + 1 as this value will now indicate the number of unique elements that are now in the array.

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for j in range(len(nums)):
            if(nums[i] != nums[j]):
                i += 1
                nums[i] = nums[j]
        
        return i + 1

Time: O(n) Space: O(1)

Approach2:

The below is quite short and it does pass the test however it does not conform to the above specified constraints which is to do it in-place while concurrently making sure that you do not use extra memory.

def removeDuplicates(self, nums):
    nums[:] = sorted(set(nums))
    return len(nums)

Time: O(n) Space: O(uniqueElements)