In theses two problems, we are asked to remove duplicates in place from a sorted array of integer. The difference is the first problem wants only unique number to remain. But the second problem allow us to have 2 duplicates but need to remove the third and beyond. We could generalize this problem to: Remove duplicates that appear more than k times(but keep the (0… k) appearance )
Use a counter to keep track of how many times we have seen the current number. If we see it more than k times, then we know it is a duplicate we need to remove.
Then we iterate through the list from i to len(nums) and compare the ith one with i – 1th element. We need to keep track of a second pointer that points to the place we need to insert the numbers. That second pointer actual_pos will always equal or less than i because if we see a duplicates more than k time in one iteration, we won’t increment actual_pos(the second pointer). And we know later if we see a non-duplicate number, we need to put it at nums[actual_pos], overwriting the duplicate.
def removeDuplicates(self, nums, k): if not nums: return 0 actual_pos = 1 count = 1 for i in range(1, len(nums)): if nums[i] == nums[i-1]: count += 1 if count > k: continue else: count = 1 nums[actual_pos] = nums[i] actual_pos += 1 return actual_pos