Two Pointers: Remove Duplicates from Sorted Array II

Question:

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3]
Explanation: Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2, and 3 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3]
Explanation: Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3, and 3 respectively. It doesn't matter what values are set beyond the returned length.

Answer:

To solve this problem, we can make use of two pointers: one to maintain the current index while traversing the array, and another to keep track of the current position where the next valid element will be placed.

Here are the steps to solve the problem:

1. Initialize two pointers, i and j, both starting at index 2 (since duplicates are allowed up to twice). Also, set a variable count to keep track of the number of occurrences of the current element.
2. Iterate through the array starting from the third element, i.e., i = 2:
   • If nums[i] is equal to nums[j-2] (i.e., it's a duplicate that has already appeared twice in the modified array), increment i and continue to the next iteration.
   • If nums[i] is not equal to nums[j-2], it means this element is a valid entry. Update nums[j] with the current value at nums[i], increment j and count, and finally increment i.
3. Return the value of j as the length of the modified array.

Here's the implementation of the solution in Python:

def removeDuplicates(nums):
    if len(nums) <= 2:
        return len(nums)

    j = 2
    count = 2

    for i in range(2, len(nums)):
        if nums[i] != nums[j-2]:
            nums[j] = nums[i]
            j += 1
            count += 1

    return count

By calling the removeDuplicates function with the given input array, it will return the length of the modified array with duplicates removed up to twice. The original array (nums) will also contain the modified elements.

nums = [1, 1, 1, 2, 2, 3]
print(removeDuplicates(nums))  # Output: 5
print(nums)  # Output: [1, 1, 2, 2, 3]

nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
print(removeDuplicates(nums))  # Output: 7
print(nums)  # Output: [0, 0, 1, 1, 2, 3, 3]

This solution has a time complexity of O(n), where n is the length of the input array, as it iterates through the array only once. It also satisfies the requirement for using O(1) extra memory.