# 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) -> bool:
lookup = dict()  #{value:index}

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

if prev != None and cur - prev <= 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 <= k` anymore.