Given a sorted array nums, 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.
How does the sorted array help us
With sorted array, we know numbers that have the same value will be all next to each other and we can know how many duplicates are there by scanning forward till we see a different numbers.
Each time we see a duplicate, we need to “squeeze” duplicates into the first appearance of the number. This squeeze will make empty space in the array.
EG: [1,2,2,3, 3] -> [1,2, EMPTY, EMPTY,3]
We need to fill the empty by the number after the duplicate.
This is done by moving all numbers after by the number of EMPTY.
We also need to accumulate the changes. If we see a duplicate at location i and squeeze it into the first appearance at location i – 1, we then need to shift all numbers after by 1. We implement this idea by shifting every number by the number of EMPTY at the beginning of the iteration.
def removeDuplicates(self, nums):
:type nums: List[int]
pos = 0
disp = 0
length = len(nums)
while pos < length: nums[pos - disp] = nums[pos] while pos < length - 1 and nums[pos] == nums[pos + 1]: pos += 1 disp += 1 pos += 1 return length - disp