Difference between n in d and n in d.keys()

• I run the python code with two different versions:

``````     d = {}
for i in range(len(nums)):
n = nums[i]
if n in d:
prev = d[n]
if i - prev <= k:
return True
d[n] = i

return False
``````

and

``````    d = {}
for i in range(len(nums)):
n = nums[i]
if n in d.keys():
prev = d[n]
if i - prev <= k:
return True
d[n] = i
return False
``````

The first one works but the second one exceeds time limit.

I know "n in d.keys()" will perform a linear search which makes the whole for look O(n^2).

But why does 'n in d' work?

• But why does 'n in d' work?

Because the makers of Python made it work?

• In python, key in dict.keys() taken O(n) time. This is because dict.keys() returns a generator and it iterates through all the keys present in dict.

However key in d is O(1). This just makes use of hash function to directly tell you whether that key is present or not in the dict.

• dict.keys() returns a generator

Actually it returns a list, as we have Python 2 here.

The Python 3 docs call it a "view object" and a "set-like object". Is it really a generator?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.