Given a sorted array nums, remove the duplicates in-place

Question

I wrote an algorithm to solve this challenge but would love some feedback on its efficiency and, if you were an interviewer, what your opinion would be on my solution. I believe my time complexity is \$O(N)\$. Is this correct?

The Task:

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return 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.

Example: Given nums = [0,0,1,1,1,2,2,3,3,4]

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set in the array beyond the returned length.

My Solution:

def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if(nums):
        IndFirstKind = IndCompare = 0
        lengthArray = len(nums)
        while(IndCompare < lengthArray):
            if nums[IndFirstKind] == nums[IndCompare]:
                IndCompare = IndCompare + 1
            else:
                if(IndFirstKind + 1 != IndCompare):
                    temp = nums[IndCompare]
                    nums[IndCompare] = nums[IndFirstKind + 1]
                    nums[IndFirstKind + 1]= temp
                IndFirstKind = IndFirstKind +1
                IndCompare = IndCompare + 1
        return IndFirstKind + 1
    return 0

Answer 1

This is a job for itertools.groupby:

i = 0
for key, _ in groupby(nums):
    nums[i] = key
    i += 1
return i

A look at the implementation of groupby shows that it allocates \$O(1)\$ extra space, as required by the problem.

The i += 1 could be avoided using enumerate, like this:

i = -1 # in case nums is empty
for i, (key, _) in enumerate(groupby(nums)):
    nums[i] = key
return i + 1

but the need for an exceptional case to handle empty input is rather inelegant.

Answer 2

while loops are not that common in Python. Instead, we prefer to iterate over elements directly using for loops.

In your case, using a running index of last modified value, you can compare the current value with the last modified to easily skip duplicates:

index_to_update = 0
for element in nums:
    if element > nums[index_to_update]:
        index_to_update += 1
        nums[index_to_update] = element

this approach store the number of elements updated in index_to_update but the first element (0 in your example) is never updated as it will never be strictly greater than the front of the list. So you need to account for it manually in your return value:

return index_to_update + 1

However, this approach lead to wrong results with empty lists, so you also have to take it into account:

def remove_duplicates(nums):
    if not nums:
        return 0

    index_to_update = 0
    for element in nums:
        if element > nums[index_to_update]:
            index_to_update += 1
            nums[index_to_update] = element

    return index_to_update + 1

Note the use of snake_case in the name of the function as per PEP8 guidelines. I also removed self to make this a regular function as there is absolutely no need to have this in a class.

Answer 3

• Flat is better than nested. Consider reverting the first if condition:

  if not nums:
      return 0
  
  # main logic goes here, less one indentation level
  

• An if-else as a body of the loop is always a red flag. In this case he body of the while loop is better expressed by another loop: we want to skip all dups of nums[intFirstKind]. Consider

      while (nums[indFirstKind] == nums[indCompare]:
          indCompare += 1
  

  You may want to go an extra mile and factor this in a function. skipDuplicates looks like a good name. BTW, what would be the parameters? what shall it return?

• Swapping nums[indCompare] with nums[indFirstKind + 1] seems like a pure waste of time. If however you insist on swapping, do it in a pythonic way:

  nums[indCompare], nums[indFirstKind + 1] = nums[indFirstKind + 1], nums[indCompare]
  

---

All that said, the solution should be along the lines of

    indCopyTo = 0
    indFirstKind = 0
    indCompare = 1

    while indCompare < len(nums):
        nums[indCopyTo] = nums[indFirstKind]
        indCopyTo += 1
        while nums[indFirstKind] == nums[indCompare]:
            indCompare += 1
        indFirstKind = indCompare
    return indCopyTo