Remove Duplicates from Sorted Array in place

remove_duplicates_sorted_arr.py

# naive solution
class Solution:
    POS_NUM = 1000
    def removeDuplicates(self, nums: List[int]) -> int:
        start = 0
        n = len(nums)
        end = n - 1
        for start in iter(lambda: start, end):
            if start > end:
                break
            if nums[start] == nums[start+1]:
                nums[start] = self.POS_NUM
            if nums[end] == nums[end-1]:
                nums[end] = self.POS_NUM
            start += 1
            end -= 1
        k = len(list(filter(lambda x: x != self.POS_NUM, nums)))
        self.mergesort(nums, 0, n - 1)
        return k
    
    def mergesort(self, nums: List[int], lo: int, hi: int) -> List[int]:
        mid = lo + (hi-lo)//2 
        if lo < hi:
            return self.sort(
                lo, mid, mid+1, hi, self.mergesort(nums, lo, mid), self.mergesort(nums, mid+1, hi), nums)
        else:
            return [nums[lo]]
    
    def sort(
        self,
        lo: int, 
        mid: int, 
        mid_hi: int, 
        hi: int, 
        left_list: List[int], 
        right_list: List[int], 
        nums: List[int]
        ) -> List[int]:
        aux = []
        left = lo
        right = mid_hi
        for _ in range(lo, hi+1):
            # print(left, lo, mid, right, mid_hi, hi, nums)
            if lo <= left <= mid and mid_hi <= right <= hi:
                if nums[left] < nums[right]:
                    aux += [nums[left]]
                    left += 1
                else:
                    aux += [nums[right]]
                    right += 1
            elif left < mid_hi:
                aux += [nums[left]]
                left += 1
            else:
                aux += [nums[right]]
                right += 1
        for idx, num in enumerate(aux):
            nums[lo+idx] = num
        return nums


# Optimal solution      
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        sane_idx = 0
        for idx in range(1, len(nums)):
            num = nums[idx]
            if nums[idx-1] != num:
                sane_idx += 1
                nums[sane_idx] = num
        return sane_idx + 1