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

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

Last updated