80. Remove Duplicates from Sorted Array II¶
Remove the duplicates in-place such that each unique element appears atmost twice. The relative order of the elements should be kept the same.
Return the number of unique elements in nums.
Do not allocate extra space for another array. Achieve this by modifying the input array in-place with $\text{O}(1)$ extra memory.
Intuition¶
- We can move an element forward by the amount of duplicates before it.
Approach¶
- We track the occurrence of an element.
- Start moving the next elements forward only if the current elements occurrence is greater 2.
Complexity¶
- Time complexity : \(\text{O}(n)\)
- We iterate the array only once
- Space complexity : \(\text{O}(1)\)
- We use no extra space, do operations in-place
Code¶
public int removeDuplicates(int[] nums) {
int occurence = 1,shift = 0;
for (int i = 1; i < nums.length; ++i) {
if(nums[i] == nums[i-1]) {
occurence++;
// only if there are more thantn 2 occurence
// we can overwrite it
if(occurence > 2) {
shift++;
continue;
}
} else {
// If the current element doesn't match the previous element
// we reset the counter
occurence = 1;
}
nums[i - shift] = nums[i];
}
return nums.length - shift;
}
Another Way
public int removeDuplicates(int[] nums) {
// This tracks where the current element must be placed
int i = 0;
for (int n : nums)
// If length is < 2
// If the current element is not equal to the element two
// places behind it
if (i < 2 || n > nums[i - 2])
nums[i++] = n;
return i;
}