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


  • 0
    Z

    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?


  • 0

    But why does 'n in d' work?

    Because the makers of Python made it work?


  • 0
    A

    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.


  • 0

    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?


Log in to reply
 

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