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]:
        i += 1
      # the number at the correct index is not the same as ours so let's swap them
        nums[i], nums[j] = nums[j], nums[i]
    # number is at correct index so move to the next number
      i += 1
  return duplicates

Type your question above this line.


1 Like


Yes, your approach is correct.