Leetcode: Detecting duplicate elements in an array within a k-element window Upon solving the problem 'contain duplicates` in leetcode:


  Given an array of integers and an integer k , find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k .
  
  Example 1:


Input: nums = [1,2,3,1] , k = 3 

Output: true


  
  Example 2:


Input: nums = [1,0,1,1] , k = 1 

Output: true


  
  Example 3:


Input: nums = [1,2,3,1,2,3] , k = 2 

Output: false




I tried best  to write a Pythonic style solution and improve the performance.

class Solution2:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -&gt; bool:
        lookup = dict()  #{value:index}

        for cur, val in enumerate(nums):
            prev = lookup.get(val)

            if prev != None and cur - prev &lt;= k: 
                #logging.debug(f"{cur - prev}")
                return True 
            lookup[val] = cur #add it to lookup 

        return False 



  Runtime: 68 ms, faster than 12.21% of Python3 online submissions for Contains Duplicate II.
  Memory Usage: 20.4 MB, less than 13.64% of Python3 online submissions for Contains Duplicate II.


I am confused about the score. I was 100% assure that it was the best possible solution.

What's the problem with my solution?
The lookup dictionary might grow as large as the size of array (all array elements are distinct). It immediately gives an \$(O(n))\$ space complexity, and has detrimental effect on the time complexity as well. It is possible to get away with \$O(k))\$.

It makes no difference if \$k \approx n\$, but boosts the performance for \$k \ll n\$ (which I presume is so for the bulk of test cases).

To keep the dictionary "small", observe that if its size reaches k, it is safe to remove the oldest element. As a side benefit, you wouldn't need to test for cur - prev &lt;= k anymore.