Problem
Given a sorted array nums, remove duplicates in-place such that each element appears only once. Return the new length. Do not allocate extra space.
Example
Input: [1,1,2]
Output: 2, with nums = [1,2,_]Input: [0,0,1,1,1,2,2,3,3,4]
Output: 5, with nums = [0,1,2,3,4,_,_,_,_,_]Solution
Use two pointers. Slow tracks where to write; fast scans for new unique values.
def remove_duplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}int removeDuplicates(vector<int>& nums) {
if (nums.empty()) return 0;
int slow = 0;
for (int fast = 1; fast < nums.size(); fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Since the array is sorted, duplicates are adjacent. Slow pointer holds the position of the last unique value. When fast finds a new value, we move slow forward and overwrite.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?