Remove Duplicates from Sorted Array II

Given a sorted integer slice, remove duplicates in-place so that each value appears at most twice. Return the new length k such that the first k elements contain the allowed values in sorted order.

Function signature

func RemoveDuplicatesSortedArrayII(nums []int) int

Inputs / outputs

• nums: sorted slice to modify in-place.
• Return: number of kept elements k; only nums[:k] is valid after the call.

Example

nums = [1,1,1,2,2,3]
After removal: nums = [1,1,2,2,3,_]
Return k = 5

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Because the array is sorted, any value beyond the second occurrence can be skipped. The easiest invariant uses the write index:

Invariant: nums[:write] contains the valid output so far, with no value appearing more than twice.

If write < 2, you can always keep the element. Otherwise, compare nums[read] to nums[write-2]:

• If they are different, the current value has appeared fewer than twice in the output, so keep it.
• If they are the same, this would be a third occurrence - skip it.

Algorithm (step-by-step)

1. If len(nums) <= 2, return len(nums).
2. Set write = 2.
3. For read from 2 to len(nums)-1:
   • If nums[read] != nums[write-2], set nums[write] = nums[read] and increment write.
4. Return write.

Correctness sketch

• Invariant: nums[:write] contains the valid output so far, with no value appearing more than twice.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

Trace (hand walkthrough)

Example input:
nums = [1,1,1,2,2,3]
After removal: nums = [1,1,2,2,3,_]
Return k = 5

Walk:
- start with first two kept: [1,1], write=2
- i=2 val=1, compare nums[write-2]=1 -> skip (would make 3 copies)
- i=3 val=2, compare nums[0]=1 -> keep -> nums[2]=2, write=3
- i=4 val=2, compare nums[1]=1 -> keep -> nums[3]=2, write=4
- i=5 val=3, compare nums[2]=2 -> keep -> nums[4]=3, write=5 => [1,1,2,2,3]

Pitfalls to avoid

• Using the wrong comparison index (the write-2 check is key).
• Failing to handle arrays of length 0, 1, or 2.
• Returning a new slice instead of the new length.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• This approach preserves order and is stable.