> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/hard/80.-remove-duplicates-from-sorted-array-ii.md).

# 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`.

```ad-attention
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

```java
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**

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