Problem
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place so that each unique element appears at most twice.Return k, the number of elements remaining after removing the extra duplicates. The first k elements of nums should contain the final result.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
nums = [1,1,1,2,2,3]Output
5
nums = [1,1,2,2,3,_]Example 2
Input
nums = [0,0,1,1,1,1,2,3,3]Output
7
nums = [0,0,1,1,2,3,3,_,_]Solution
This solution uses the Two Pointer pattern. Since the array is already sorted, duplicates are next to each other.We maintain a pointer
k representing the position where the next valid element should be placed. An element can be kept if either fewer than two elements have been stored so far, or it is different from the element located two positions before.
Checking
nums[i] != nums[k - 2] ensures that the same value cannot appear more than twice.
class Solution {
public int removeDuplicates(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
// Keep the element if fewer than two elements exist
// or if it is different from the element two positions back.
if (k < 2 || nums[i] != nums[k - 2]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}Complexity
We traverse the array once, so the time complexity isO(n), where n is the length of the array.
The solution modifies the array in-place and uses only a few variables, so the extra space complexity is
O(1).