Easy Slow-Fast Write Two Pointers
In plain English: Remove duplicate values from a sorted list in-place and return how many unique values remain.
Slow pointer marks the write position, fast pointer scans ahead. When fast finds a new value, write it at slow+1 and advance slow. The sorted order guarantees duplicates are adjacent.
Prompt
Given a sorted array nums, remove the duplicates in-place such that each element appears only once. Return the new length.
Try to write it from scratch before scrolling down.
Solution
def remove_duplicates(nums):
if not nums:
return 0
slow = 0 # slow = next write position for a unique value
for fast in range(1, len(nums)): # fast scans ahead for new values
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Test: nums = [1,1,2]; remove_duplicates(nums) == 2; nums[:2] == [1,2]
# Test: nums = [0,0,1,1,1,2,2,3,3,4]
# remove_duplicates(nums) == 5; nums[:5] == [0,1,2,3,4]