Menu
I came across a question when I solved this LeetCode problem. Although my solution got accepted by the system, I still do not have any idea after searching online for the following question:
What is the time complexity of dict.keys() operation?
Does it return a view of the keys or a real list (stores in memory) of the keys?
904
If we explain the difference by Big O concepts, dictionaries have constant time complexity, O(1) while lists have linear time complexity, O(n).
Python Dictionary keys() The keys() method extracts the keys of the dictionary and returns the list of keys as a view object.
The in operator for dict has average case time-complexity of O(1).
keys() would take O(n) time to find nums[i] in the list of keys thus making the time complexity O(n^2).
In Python 2, it's O(n), and it builds a new list. In Python 3, it's O(1), but it doesn't return a list. To draw a random element from a dict's keys, you'd need to convert it to a list, and that conversion is O(n).
It sounds like you were probably using random.choice(d.keys()) for part 3 of that problem. If so, that was O(n), and you got it wrong. You need to either implement your own hash table or maintain a separate list of elements, without sacrificing average-case O(1) insertions and deletions.
75
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
