Delete duplicates sorted II

Remove duplicates in a sorted list so each value appears at most twice, in place.

arrays two-pointers in-place

Write a function `remove_duplicates(nums)` that takes a list of integers sorted in non-decreasing order and removes duplicates in place so that each unique element appears at most twice. The relative order of the elements must be preserved. The function should return the new length of the list. Do not allocate extra space for another list; you must do this by modifying the input list in place with O(1) extra memory. The first `k` elements of `nums` after the function returns should hold the final result, and it does not matter what you leave beyond the first `k` elements.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
Input is sorted in non-decreasing order.
Expected time complexity O(n), space O(1).

Example

>>> nums = [1,1,1,2,2,3]
>>> k = remove_duplicates(nums)
>>> k
5
>>> nums[:k]
[1,1,2,2,3]

>>> nums = [0,0,1,1,1,1,2,3,3]
>>> k = remove_duplicates(nums)
>>> k
7
>>> nums[:k]
[0,0,1,1,2,3,3]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a slow pointer to decide where to place the next allowed element.

Iterate with a fast pointer; allow an element if it is not the third consecutive duplicate.

Because the list is sorted, duplicates appear consecutively. Track how many times the current value has appeared.

You can overwrite positions earlier in the list because you only read ahead with the fast pointer.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.