Inaccuracy in file remove_duplicates_list.py

[Mahyar-GH]

Details
I'm pretty sure remove_duplicates_list.p is not O(n) time complexity.
Because of this line:

DSA/algorithms/Python/arrays/remove_duplicates_list.py

Line 25 in d3c2184

if values[index_position] in values[0:index_position]:

[welcome]

Thanks for opening your first issue here! Be sure to follow the issue template!

[noor-malaika]

I agree that the time cmplx is not O(n) but i think the reason is not the comparison statement.

The line of list.remove(value) looks for the value in list while it is nested in a loop of n iters, so in worst case it will have a complexity of O(n^2).

[Mahyar-GH]

I agree that the time cmplx is not O(n) but i think the reason is not the comparison statement.

The line of list.remove(value) looks for the value in list while it is nested in a loop of n iters, so in worst case it will have a complexity of O(n^2).

To my knowledge using the in keyword followed by a python list is O(n).
If it was followed a set though, it would have been constant time.

Anyways you are also correct the line below is itself O(n). I haven't paid attention to that.

[vishalkhyatriya12]

Hi this is vishal!!
lets make it more simpler
here is the code
sample_case = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

def make_distinct(values: list) -> list:
"""
Remove duplicate elements in an array inplace without creating new array.
"""
index = len(values) - 1
while index > 0:
if values[index] in values[:index]:
values.pop(index)
index -= 1

return values

if name == "main":
print(make_distinct(sample_case))

use while instead of for loop and finally o(n)