Leetcode 80: Remove Duplicates from Sorted Array II

This is a variant on Remove Duplicates from Sorted Array which for which I put a solution in this link.

This exercise is very similar to Remove Duplicates from Sorted Array (I), but this time duplicates are allowed, and elements can occur at most 2 times.

a. Update to the simple remove duplicates algorithm

We can simply follow the same pattern as in the previous exercise, but instead of comparing nums[i-1] and nums[i], we compare nums[i-2], nums[i-1] and nums[i].

public int removeDuplicates(int[] nums) {
    int n = nums.length;
    if (n < 3) {
        return n;
    }
    int prev1 = nums[0];
    int prev2 = nums[1];
    int i = 2;
    int j = 2;
    while (j < n) {
        if (prev1 == prev2 && nums[j] == prev1) {
            j++;
        } else {
            prev1 = prev2;
            prev2 = nums[j];
            nums[i] = nums[j];
            i++;
            j++;
        }
    }
    return i;
}

b. Time and space complexity

Just like the previous algorithm, time complexity is O(n) and space complexity is O(1).