Remove Duplicates from Sorted Array II
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. Return k after placing the final result in the first k slots of nums. 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 k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
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 k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^4numsis sorted in non-decreasing order.
## Solution to Remove Duplicates from Sorted Array II
This problem requires us to modify the input array in-place such that each unique element appears at most twice, preserving the original order. We aim to return the new length of the modified array.
### 1. Naive Approach
One straightforward but not in-place approach would be to create a new list, iterate through the original array, and add elements to the new list only if they appear less than twice. This approach, however, violates the in-place constraint.
### 2. Optimal Approach
We use a two-pointer technique to solve this in-place. We maintain a `slow` pointer that points to the position where the next non-duplicate element should be placed and a `fast` pointer to iterate through the array. We keep track of the count of each element. If an element appears less than or equal to twice, we move it to the position pointed by `slow` and increment `slow`.
Here's the code:
```python
def removeDuplicates(nums):
if not nums:
return 0
slow = 0
count = 1
for fast in range(1, len(nums)):
if nums[fast] == nums[slow]:
count += 1
if count <= 2:
slow += 1
nums[slow] = nums[fast]
else:
count = 1
slow += 1
nums[slow] = nums[fast]
return slow + 1
Example:
Consider nums = [1,1,1,2,2,3]
slow = 0,count = 1fast = 1,nums[fast] == nums[slow],count = 2,slow = 1,nums = [1,1,1,2,2,3]fast = 2,nums[fast] == nums[slow],count = 3. Sincecount > 2, we skip.fast = 3,nums[fast] != nums[slow],count = 1,slow = 2,nums = [1,1,2,2,2,3]fast = 4,nums[fast] == nums[slow],count = 2,slow = 3,nums = [1,1,2,2,2,3]fast = 5,nums[fast] != nums[slow],count = 1,slow = 4,nums = [1,1,2,2,3,3]
The function returns slow + 1 = 5.
3. Big(O) Runtime Analysis
The optimal solution iterates through the array once using a single for loop. Therefore, the time complexity is O(n), where n is the length of the input array.
4. Big(O) Space Usage Analysis
The solution operates in-place, meaning it does not use any extra space that scales with the input size. It only uses a few integer variables (slow, count, and fast), which take constant space. Hence, the space complexity is O(1).
5. Edge Cases and Considerations
- Empty Array: If the input array is empty, the function should return 0 immediately, which is handled by the initial check
if not nums: 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 will correctly return the length of the array.
- Array with All Same Elements: If the array contains only the same element repeated more than twice, the function will reduce the array to contain only two instances of that element.
