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 being1,1,2,2and3. 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 numsin 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.

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.

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.

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