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.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.