Hi Can you please review the following solution I came up with for this question? This doesn’t use any extra space and is O(n) for time complexity as well.
def find_duplicates(lst):
“”"
Function to find duplicates in a given lst
:param lst: A list of integers
:return: A list of duplicate integers with no repetition
“”"
n = len(lst)
result = set() # A list to store duplicates
for i in range(n):
curr_num = lst[i]%n
orig_num_at_curr_num_idx = lst[curr_num]%n
number_of_times_curr_num_seen = lst[curr_num] // n
lst[curr_num] = orig_num_at_curr_num_idx + (n*(number_of_times_curr_num_seen+1))
if number_of_times_curr_num_seen >= 1:
result.add(curr_num)
return list(result)
We have run [1,2,3] input on your code, it returns [2] but there is no duplicates there in input. The same input is also passed to the lesson’s solution, works fine by returning [].