# 80 Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":\
What if duplicates are allowed at most twice?

For example,\
Given sorted array 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`. It doesn't matter what you leave beyond the new length.

**Note:** Since I did not understand problem completely at first, I thought it was also worth mentioning here that the idea is credit the new size of `nums`in such a way so that who ever uses this function can call it, and then simply get the subvector `vector<int>(nums.begin(), nums.begin() + count)`.

I thought it was a pretty cool problem so I tried to optimize my solution until I reached the 90% performance threshold.

**Attempt 1:** O(n^2) time and O(n) space. Maintain a hash for the duplicates up to a count of 2, or otherwise erase the number from `nums`. This is a poor implementation because it does not use the fact that the array is *sorted*, and it calls erase on a contiguous data structure. Bad bad.

```cpp
int removeDuplicates(vector<int>& nums) {
    unordered_map<int, int> int_freq;
    int_freq.reserve(nums.size());

    for (int i = 0; i < nums.size(); i++) {
        if (int_freq.find(nums[i]) != int_freq.end()) {
            if (int_freq[nums[i]] <= 1) {
                int_freq[nums[i]]++;
            }
            else {
                nums.erase(nums.begin() + i);
                i--;
            }
        }
        else
            int_freq.insert({ nums[i], 1 });
    }

    return nums.size();
}
```

**Attempt 2:** O(2n) time and O(1) space. Iterate through the numbers and accept the ones that don't contain the same elements 2 indices before it.

```cpp
int removeDuplicates(vector<int>& nums) {
    int it = 0;
    for (int n : nums) {
        // before a duplicate is even possible or
        // if 2 elements before is smaller
        if (it < 2 || nums[it - 2] != n)
            nums[it++] = n;
    }
    return it;
}
```

**Attempt 3:** O(n) time and O(1) space. Same idea, just separate the logic to start at index 2, rather than zero.

```cpp
int removeDuplicates(vector<int>& nums) {
    int it = 2;
    const size_t size = nums.size();
    for (int j = it; j < size; j++) {
        int check = nums[j];
        if (nums[it - 2] != check)
            nums[it++] = check;
    }

    return it > nums.size() ? nums.size() : it;
}
```