1. Remove Duplicates from Sorted Array (LeetCode)
Model answer
The task
Given a sorted list of integers, modify it in place so each distinct value appears once in the front. Return the length of that unique prefix.
Key idea
Because the values are sorted, duplicates are adjacent. Keep a read pointer to scan the list and a write pointer for the next position where a new value belongs.
Approach
- If the list is empty, return
0. - Start the write pointer at
1, since the first value is already unique. - Scan from left to right.
- When the current value differs from the last value written, copy it to the write position and advance the pointer.
- Return the write pointer as the unique-prefix length.
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
write = 1
# Copy each newly encountered value into the unique prefix.
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write
Complexity:
- Time: O(n), where
nis the length of the list. - Space: O(1), since the list is modified in place using only a fixed number of variables.
Common follow-ups
- What if the list is not sorted? Use a set to track seen values while compacting unique values in their original order.
- What if each value may appear at most twice? Write a value when fewer than two values have been written, or when it differs from the value two positions back.
- What if the list is very large and cannot fit in memory? Process sorted chunks while carrying the last value across chunk boundaries.