Leetcode: Detecting duplicate elements in an array within a k-element window

Question

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?

Answer 1

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.