How do you remove duplicates from a sorted array in place, and why does that approach work?
You use two indexes. One walks through the list, and the other marks where the next different value should be written.
So how does it work? The list is sorted, so every copy of a value is next to the others. You keep a write position that starts at the second item, and you walk a read position through the list. Whenever you find a value that is different from the one before it, you write it at the write position and move the write position along. Everything that you skip over is a duplicate.
And why does that work? Because of the sorted order. If the list is sorted then all the copies of a value are together, so once you have seen one copy you know that every copy after it is the same, until the value changes. You never have to look back, and you never have to remember what you have already seen.
def remove_duplicates(nums):
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
So it is O of n for the time and O of 1 for the space, because you never make a new list. That is the point of doing it in place.
The next two questions in this topic ask for the function itself and for a version that also counts.