80. Remove Duplicates From Sorted Array 2

Problem Statement in English

You’re 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.

Approach

We can maintain a pointer l that represents the position where the next unique element should be placed. We can iterate through the array with another pointer r.

If the current element at r is not equal to the element at l - 2, we can place it at position l and increment l. This way, we ensure that each unique element appears at most twice.

And we’re done!

Solution in Python

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        l = 2
        for r in range(2, len(nums)):
            if nums[r] != nums[l - 2]:
                nums[l] = nums[r]
                l += 1

        return l

Complexity

• Time: $O(n)$
  Since we are iterating through the entire array once, the time complexity is linear with respect to the number of elements in the array.
  

• Space: $O(1)$
  Since we are using a constant amount of extra space (only a few variables), the space complexity is constant.

And we are done.