Remove Duplicates from Sorted Array II

06/28/2016 Array Two Pointers

Question

QFollow 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

Result: Accepted Time: 8 ms

Here should be some explanations.

int removeDuplicates(int* nums, int numsSize) {
    if(numsSize < 3)
        return numsSize;
    int cnt = 0;
    for(int i = 2; i < numsSize; i++)
        if(nums[i]!=nums[cnt])
            nums[2+cnt++] = nums[i];
    return cnt+2;
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: