Problem

Solution

Intuition

This problem initially seems like a two pointer problem as we want to keep track of the position of “good” items while continuing to iterate through the array.

Approach

This problem is solved using a two pointer approach, similar to a slow pointer and fast pointer approach. If the fast pointer runs into a unique element (i.e.: nums[i] != nums[i-1]), we put the unique element to where the slow pointer is and then move the slow pointer forwards. Otherwise, while the fast pointer continues to run into duplicates, the slow pointer will wait until a new distinct element is ready to be placed in the front of the array. Remember that this only works because the array is non-decreasing and therefore we are able to track the previously seen elements by just relying on a greater number to show up and we don’t need to remember all of the previous values. Also keep in mind this solution works because the in-place transformation of nums allows for the end values to remain with any possible value and therefore we only leave the last duplicates in place and can overwrite early duplicates.

Complexity

• Time complexity: $O(n)$ time complexity. We only iterate through the array once and perform a constant time operation. It is a two pointer solution; however, each one only iterates fowards so there is no repeated looping work.
• Space complexity: $O(1)$ space complexity. We only use pointers and no data structures.

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 1
        for fast in range(1, len(nums)):
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
        return slow