Naive Solution

A brute force approach would involve creating a new array, iterating through the original array, and adding elements to the new array only if they appear less than or equal to twice. This approach is straightforward to understand but requires extra space.

Code (Python)

def remove_duplicates_naive(nums):
    new_nums = []
    counts = {}
    for num in nums:
        if num not in counts:
            counts[num] = 0
        counts[num] += 1
        if counts[num] <= 2:
            new_nums.append(num)
    nums[:] = new_nums  # Modify nums in-place
    return len(nums)

Big O Analysis

• Time Complexity: O(n), where n is the length of the input array, as we iterate through the array once.
• Space Complexity: O(n), as we create a new array new_nums that, in the worst case, could store all elements of the original array.

Optimal Solution

The optimal solution uses a two-pointer approach to modify the array in-place. We maintain a slow pointer (k) that points to the next available position in the modified array and a fast pointer (i) that iterates through the original array. We copy the element at nums[i] to nums[k] only if the element appears less than twice in the modified part of the array.

Code (Python)

def remove_duplicates(nums):
    k = 0  # Index for the modified array
    for i in range(len(nums)):
        if k < 2 or nums[i] != nums[k - 2]:
            nums[k] = nums[i]
            k += 1
    return k

Explanation

1. Initialize k = 0. The k pointer indicates the index up to which the array has been modified and contains the desired elements.
2. Iterate through the array with index i.
3. The condition k < 2 or nums[i] != nums[k - 2] checks whether we can add nums[i] to the modified array.
   • If k < 2, it means we have less than two elements in the modified array, so we can safely add the current element.
   • If nums[i] != nums[k - 2], it means the current element is different from the element two positions before k, so it won't violate the at-most-twice rule.
4. If the condition is met, we copy nums[i] to nums[k] and increment k.
5. Return k, which represents the length of the modified array.

Big O Analysis

• Time Complexity: O(n), where n is the length of the input array, as we iterate through the array once.
• Space Complexity: O(1), as we modify the array in-place and use only a constant amount of extra space.

Edge Cases

• Empty Array: If the input array is empty, the function should return 0.
• Array with One or Two Elements: If the array has one or two elements, no duplicates need to be removed, and the function should return the original length.
• Array with All Same Elements: If all elements in the array are the same, the function should return 2, keeping only the first two occurrences.
• Array with No Duplicates: If there are no duplicates, the function should return the original length of the array.