Problem Description
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. Return the number of elements k after placing the final result in the first k slots of nums.
Key Insights
- The array is already sorted, which simplifies the problem since duplicates will be adjacent.
- We need to maintain the relative order of elements while ensuring that no element appears more than twice.
- The solution must be implemented in-place without using extra space for another array.
Space and Time Complexity
Time Complexity: O(n) - We traverse the array at most twice. Space Complexity: O(1) - We use a constant amount of extra space.
Solution
The problem can be solved using a two-pointer technique. One pointer (i) will traverse the array, while the other pointer (k) will track the position to place the next valid element. We'll loop through the array, allowing at most two occurrences of each element. When we encounter an element that has already appeared twice, we skip it. This approach ensures that we modify the array in-place and maintain the required order.