Remove Duplicates from Sorted Array

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.

Solution: Using selection sort with a flag

We use a flag to mark whether the duplicate has appeared twice, if so we can remove the new element.

int removeDuplicates(vector<int>& nums) {
    if(nums.empty()) return 0;

    bool flag = false;
    int index = 0;
    for(int i=1; i<nums.size(); i++) {
        if(nums[index] < nums[i]) {
            index += 1;
            swap(nums[index], nums[i]);
            flag = false;
        } else if(!flag) {
            index += 1;
            swap(nums[index], nums[i]);
            flag = true;
        }
    }
    return index+1;
}

Solution: Using simple compare

We can just compare the element with the second last element, because the last two element might be the same. In this way, we can ensure that there won't be more than two duplicate.

int removeDuplicates(vector<int>& nums) {
    int index = 0;
    for(auto num: nums) {
        if(index < 2 || nums[index-2] < num) {
            nums[index++] = num;
        }
    }
    return index;
}