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.