Given a sorted array nums, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be preserved.

  • Return Value: The function should return the new length of the array after removing duplicates.
  • Constraints:
    • Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
    • The elements beyond the returned length do not matter.
  • Example:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. The values beyond the returned length do not matter.

Solution

  • Approach: We can use a two-pointer technique.
    • Initialize i as the slow-pointer (index to place the next unique element) to 0.
    • Initialize j as the fast-pointer (to iterate through the array) to 1.
    • Iterate j from the second element to the end of the array.
    • If nums[j] is different from nums[i], it means we found a new unique element. Increment i, then set nums[i] = nums[j].
    • If nums[j] is the same as nums[i], it's a duplicate, so we just increment j to skip it.
    • The final length will be i + 1.
  • Code (Python):
class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0

        i = 0  # Slow pointer, for unique elements
        for j in range(1, len(nums)): # Fast pointer, to iterate
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1