# 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.

1 Like

@Demos