Problem

  • Given a sorted array \(nums\), remove the duplicates in-place such that each element appears only once and returns the new length.
  • Do not allocate extra space for another array, you must do this by modifying the input array in-place with \(O(1)\) extra memory.
  • See problem on LeetCode.

Algorithm

  • Since the array is already sorted, we can keep two pointers \(i\) and \(j\), where \(i\) is the slow-runner while \(j\) is the fast-runner. As long as \(nums[i] = nums[j]\), we increment \(j\) to skip the duplicate.
  • When we encounter \(nums[j] \neq nums[i]\), the duplicate run has ended so we must copy its value to \(nums[i + 1]\). \(i\) is then incremented and we repeat the same process again until \(j\) reaches the end of array.

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        """
        @param a list of integers
        @return an integer
        """
        
        # Handle the special case that A is empty    
        if not nums: # or "if not len(nums)" or "if len(A) == 0"
            return 0
        	
        i = 0
        for j in range(1, len(nums)):
            # Not a duplicate item            
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]

        return i + 1

Complexity analysis

  • Time complexity: \(O(n)\). Assume that \(n\) is the length of array. Each of \(i\) and \(j\) traverses at most \(n\) steps.
  • Space complexity: \(O(1)\).