2
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.