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.
Input: nums = [1,1,2,2,2,2,2,3,3,3,3,3]
Output: 2, nums = [1,1,2,2,3,3]Return the number of unique elements in nums.
!!! attention Do not allocate extra space for another array. Achieve this by modifying the input array in-place with 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 :
- We iterate the array only once
- Space complexity :
- 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;
}