Drop Sorted Duplicates
Problem
A list of integers arrives sorted in non-decreasing order, so equal values sit next to each other in runs. Compact the list in place so every distinct value appears exactly once, in the original order. Return the count k of distinct values; the first k slots must hold them, and whatever remains after those slots is ignored.
Examples
Input: nums = [1, 1, 2, 3, 3, 3]
Output: 3, and nums begins with [1, 2, 3]Input: nums = [4, 4, 4]
Output: 1, and nums begins with [4]
Why: one long run collapses to a single valueInput: nums = []
Output: 0
Why: edge case, an empty list keeps nothingHints
0 / 3
Sorting has already done the hard part: a duplicate can only sit directly beside its twin, so you never have to search the whole list.
Keep two positions moving at different speeds over the same list, one that inspects every element and one that marks where the next keeper belongs.
Advance the reading position across the list. Whenever the value there differs from the last value you kept, copy it to the writing position and push that position forward. The writing position ends up equal to the number of distinct values.
Solution
Two indexes walk the same list: a reader visits every element, and a writer marks the slot for the next distinct value. Because equal values are adjacent in sorted input, the reader only needs to compare against the last kept value to detect a new run. Copying happens only at run boundaries, so no extra list is allocated. Time is O(n) and space is O(1).
def compact_sorted(nums):
if not nums: # nothing to keep in an empty list
return 0
write = 1 # slot for the next distinct value
for read in range(1, len(nums)):
# sorted input means a new value shows up only at a run boundary
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
a = [1, 1, 2, 3, 3, 3]
print(compact_sorted(a), a[:3]) # -> 3 [1, 2, 3]
b = [4, 4, 4]
print(compact_sorted(b), b[:1]) # -> 1 [4]
print(compact_sorted([])) # -> 0Stuck on the idea rather than the code? Two Pointers covers it.