[leetcode] 26. Remove Duplicates from Sorted Array

Question

Given the array integer which is sorted by ascending. It may have duplicated numbers so what you need to do is to remove them and return the length of unique numbers.

But, one more thing you need to do is that you also remove duplicated numbers from the array and put unique numbers left-aligned without using another memory space.

Solution

My answer is to use two pointers. I defined two variables called "left" and "right". The initial value of left is 0 and right's is 1. We traverse all numbers from beginning to end by moving these pointers. If the index of letters between them is the same, the only right pointer moves to the next. If not, switch them and both move to the next.

Submission

Here is result.

Runtime: 88 ms, faster than 65.88% of Python3 online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 15.7 MB, less than 48.13% of Python3 online submissions for Remove Duplicates from Sorted Array.

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

I travel all numbers once from left to right. So, time complexity is O(n) and there is no space so space is O(1).

Here is my python code.

def removeDuplicates(self, nums: List[int]) -> int:
    left: int = 0
    right: int = 1
    while right < len(nums):
        if nums[left] != nums[right]:
            left += 1
            nums[left] = nums[right]
        right += 1
    nums = nums[:left + 1]
    return left + 1