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

# Remove Duplicates from Sorted Array II

Given a sorted array *nums*, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that duplicates appeared at most \_twice\_and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm)with O(1) extra memory.

**Example 1:**

```
Given 
nums
 = 
[1,1,1,2,2,3]
,

Your function should return length = 
5
, with the first five elements of 
nums
 being 
1, 1, 2, 2
 and 
3
 respectively.

It doesn't matter what you leave beyond the returned length.
```

**Example 2:**

```
Given 
nums
 = 
[0,0,1,1,1,1,2,3,3]
,

Your function should return length = 
7
, with the first seven elements of 
nums
 being modified to 
0
, 
0
, 
1
, 
1
, 
2
, 
3
 and 
3
 respectively.

It doesn't matter what values are set beyond the returned length.
```

**Clarification:**

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

```
// 
nums
 is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to 
nums
 in your function would be known by the caller.
// using the length returned by your function, it prints the first 
len
 elements.
for (int i = 0; i 
<
 len; i++) {
    print(nums[i]);
}
```

## Analysis

[Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) 的后续，同样是在sorted array中去除重复元素，这里不同在于能够允许k（k=2）个重复。

那么就可以利用一个额外的counter，来计数当前重复元素的次数，达到2以后就跳过store或者swap的过程，直到遇到下一个新的非重复的元素。

其实可以跳出每个pointer移动的细节，如下解法提供了一种另辟蹊径的[通用思路](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27976/3-6-easy-lines-C%2B%2B-Java-Python-Ruby) （@StefanPochmann）：

> Just go through the numbers and include those in the result that haven't been included twice (or K times) already.

```java
class Solution {

    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }

    public int removeDuplicates(int[] nums, int k) {
        int i = 0;
        for (int n : nums) {
            if (i < k || n != nums[i-k]) {
                nums[i++] = n;   
            }
        }
        return i;
    }
}
```

通过以上解法可以发现，其实两个指针的解法，真的很灵活。而且，不一定要同时用while语句，一个指针用for-loop遍历全部，另一个内部循环个根究条件移动也是可行的。

## Solution

Two Pointers (6ms, 96.59%)

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int count = 1;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] == nums[i]) {
                if (count < 2) {
                    i++;
                    nums[i] = nums[j];
                    count++;
                } else {
                    continue;
                }
            } else if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
                count = 1;
            }
        }
        return i + 1;
    }
}
```

\-- for k-allowed k duplication - generic solution

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }

    public int removeDuplicates(int[] nums, int k) {
        int i = 0;
        int count = 1;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] == nums[i]) {
                if (count < k) {
                    i++;
                    nums[i] = nums[j];
                    count++;
                } else {
                    continue;
                }
            } else {
                i++;
                nums[i] = nums[j];
                count = 1;
            }
        }
        return i + 1;
    }
}
```

LeetCode 上的一个对于Remove Duplicates from Sorted Array I，II [通用的答案](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27970/Share-my-O%28N%29-time-and-O%281%29-solution-when-duplicates-are-allowed-at-most-K-times)：（k = 1, or, k = 2）

O(n) time, and O(1) space

> we need a count variable to keep how many times the duplicated element appears, if we encounter a different element, just set counter to 1, if we encounter a duplicated one, we need to check this count, if it is already k, then we need to skip it, otherwise, we can keep this element.

```java
int removeDuplicates(int A[], int n, int k) {

            if (n <= k) return n;

            int i = 1, j = 1;
            int cnt = 1;
            while (j < n) {
                if (A[j] != A[j-1]) {
                    cnt = 1;
                    A[i++] = A[j];
                }
                else {
                    if (cnt < k) {
                        A[i++] = A[j];
                        cnt++;
                    }
                }
                ++j;
            }
            return i;
}
```

\***Most Simpler Solution (6ms)**

```java
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int n : nums)
            if (i < 2 || n != nums[i-2])
                nums[i++] = n;
        return i;
    }
```

**Could be applied to k - general solution**

```java
class Solution {

    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }
    public int removeDuplicates(int[] nums, int k) {
        int i = 0;
        for (int n : nums) {
            if (i < k || n != nums[i-k]) {
                nums[i++] = n;   
            }
        }
        return i;
    }
}
```

Another implementation:

```java
class Solution {
    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }
    private int removeDuplicates(int[] nums,int k) {
        // if array size is less than k then return the same
        if(nums.length < k) {
            return nums.length;
        }
        int i, j;
        // start from index k
        for(i = k, j = k ; j < nums.length; j++) {
            if(nums[i - k] != nums[j]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}
```

## Reference

<https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27976/3-6-easy-lines-C%2B%2B-Java-Python-Ruby>

<https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27970/Share-my-O(N)-time-and-O(1)-solution-when-duplicates-are-allowed-at-most-K-times>