Remove duplicates in place
We'll cover the following
In a sorted array, keep one copy of each value at the front, without using extra space.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
slow10
11
12
23
24
35
46
47
48
49
410
411
412
513
514
515
616
617
618
619
The first value is always kept. slow marks the end of the unique part, fast scans ahead.
1 / 21
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | fast reads every item once; writes are in place. |
In Python
def remove_duplicates(nums):
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1Summary: say it in the interview
- Both pointers start on the left. fast reads every value. slow marks where the next unique value should be written. A different kind of two pointers: same direction, different speeds.
- Time O(n), space O(1). fast reads every item once; writes are in place.