educative.io

Educative

Slight optimisation to the algorithm

The provided solution runs at O(n) asymptotically but to be specific it runs at O(n) + O(n - 1) + O(n - 1).

We can improve that by omitting the last loop and just adding the duplicates as we encounter them in the main while loop, that would give us a time complexity of O(n - 1) + O(n - 1)

def find_all_duplicates(nums):
  duplicates = []
  i, n = 0, len(nums)

  while i < n:
    # correct index of num at index i
    j = nums[i] - 1
    # number at wrong inded
    if i != j:
      # same number as our number exists at the correct index 
      # thus confirming we have a duplicate and adding to our list of duplicates
      # we are also done with the current number so we move our pointer
      if nums[i] == nums[j]:
        duplicates.append(nums[i])
        i += 1
      # the number at the correct index is not the same as ours so let's swap them
      else:
        nums[i], nums[j] = nums[j], nums[i]
    # number is at correct index so move to the next number
    else:
      i += 1
  
  return duplicates

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5115834240335872

1 Like

@Demos

Yes, your approach is correct.