Remove Duplicates from Sorted Array
Easy· slow and fast· in-place
Problem
Given a sorted array, remove repeated values in place so that each distinct value appears once, keeping their order. Return k, the number of distinct values; the first k slots of the array must hold them.
Examples
Input: nums = [1,1,2,3,3,3,4]
Output: 4, nums starts with [1,2,3,4]
Whatever is left after the first four slots does not matter.
Input: nums = [0,0]
Output: 1, nums starts with [0]
Constraints
- • 1 <= nums.length <= 3 * 10^4
- • nums is sorted in non-decreasing order
Hints & approach
Hint 1
Since the array is sorted, duplicates are always adjacent.
Hint 2
Keep a slow pointer for where the next unique value goes and a fast pointer for reading.
Approachtry the hints first
Let k = 1 be the write position (the first element is always kept). Scan i from 1 to n - 1; when nums[i] differs from nums[k - 1], copy it to nums[k] and increment k. Because the array is sorted, comparing with the last kept value is enough to detect a new distinct value. Return k.
Time O(n) · Space O(1)