DEV Community

loading...

Discussion on: Daily Coding Problem #1

rrampage profile image
Raunak Ramakrishnan

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.

Thread Thread
cwetanow profile image
Ivan Author

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

Thread Thread
rrampage profile image
Raunak Ramakrishnan

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