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.

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;
}