re: Daily Coding Problem #1 VIEW POST

TOP OF THREAD FULL DISCUSSION
re: Incorrect. s is a set. The in (contains) for s is O(1). It is traversing through the list exactly once. How are you getting O(NĀ²)?

o_O

If in for sets in python is O(1) then I was incorrect. Do you have a prooflink? I am struggling to imagine an implementation for set that provides a O(1) lookup.

This page lists the complexities of the major data structures in Python. Sets and dicts have a similar implementation. The lookup is O(1) in average case, the hash function can lead to O(n) lookups in pathological cases.
Also, amortized O(n) is possible when dicts/sets are resized when adding new elements

PS: For this specific problem, we do not need to use a set as an array will do i.e keys are integers. So if the range of numbers is limited, array index provides a good hash function.

I do not think there is an upper range of numbers and they are also not subsequent, so using an array like a hashset is not usefull in this particular situation

Yes. I was not sure of that constraint. In that case, set is better.

code of conduct - report abuse