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