26. Remove Duplicates From Sorted Array

Problem Statement in English

You’re given an integer array nums sorted in non-decreasing order. Remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Approach

Since the array is sorted, we can use 2 different pointers to remove duplicates in-place.

We will maintain a pointer k that keeps track of the position of the next unique element. We will iterate through the array and whenever we find a new unique element, we will place it at the position indicated by k and increment k.

Finally, we will return k, which represents the number of unique elements in the modified array.

And we’re done!

Solution in Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 1

        for i in range(1, len(nums)):
            if nums[i - 1] != nums[i]:
                nums[k] = nums[i]
                k += 1
        
        return k

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 modifying the input array in place and not using any additional data structures that scale with input size, the space complexity is constant.

And we are done.