Remove Duplicates From Sorted Array Ii - Leetcode Solution

Problem Statement:

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.

Clarification:

Confused why the returned value is an integer, but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally, we can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

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.

Constraints:

1. 0 <= nums.length <= 3 * 104
2. -10^4 <= nums[i] <= 10^4
3. nums is sorted in ascending order.

Solution:

In this problem, we are asked to remove duplicates from a sorted array in-place such that duplicates should appear at most twice. This can easily be done using the two-pointer approach. We will use two pointers, i and j. The pointer i will keep track of the unique elements in the array, and the pointer j will traverse the array. If the element at j is the same as the previous element, we will increment the count and move j. If the count is less than equal to 2, we will copy the element at j to the position of i and increment both pointers. If the count is greater than 2, we will only increment j until we find a different element. Once the j pointer reaches the end of the array, we can return the value of i as the new length of the array.

Code:

Here is the Python code to solve the problem:

class Solution: def removeDuplicates(self, nums: List[int]) -> int: # Initialize two pointers. i, count = 0, 1

    # Start iterating from second element
    for j in range(1, len(nums)):
  
        # If the current element is a duplicate, increment the count
        # If the count is less than or equal to 2, copy the element at j to the position of i and increment i
        if nums[j] == nums[j-1]:
            count += 1
        else:
            count = 1
  
        if count <= 2:
            nums[i] = nums[j]
            i += 1
  
    return i

Time Complexity:

The time complexity of the above code is O(n), where n is the length of the input array. This is because we are traversing the entire array only once.

Space Complexity:

The space complexity of the above code is O(1), because we are not using any extra space and are modifying the input array in place.

Therefore, this solution meets the requirements specified in the problem statement.

1