The problem
A sorted list may contain duplicates. Remove them in place so each value appears once at the front, and return how many unique values there are.
Input: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] Output: 5 (front becomes 0, 1, 2, 3, 4)
Picture it
Picture a reader and a writer on a sorted shelf. The reader looks at every book; whenever it finds a value different from the last one written, the writer puts it in the next slot. Copies sit next to each other, so this catches them all.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Two pointers (read, write) on a sorted list. O(n), O(1).
Python solution
def remove_duplicates(nums):
w = 1
for r in range(1, len(nums)):
if nums[r] != nums[w - 1]:
nums[w] = nums[r]
w += 1
return wIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.