My simple python code, linear time, 48ms accepted


  • 1
    A
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @return {boolean}
        def containsNearbyDuplicate(self, nums, k):
            if nums is None:
                return False
    
            coll = {}
            res = False
            for i in xrange(len(nums)):
                if coll.get(nums[i]) is None:
                    coll[nums[i]]=i
                else:
                    if i-coll[nums[i]]<=k:
                        res = True
                    else:
                        coll[nums[i]] = i
    
            return res

  • 0
    X

    You don't have to iterate till the very end - enough to return as soon as a duplicate is found. Also you don't have two searches - can play around with defaultdict or something to both check&insert in one search.


  • 0
    A

    I agree with this point "You don't have to iterate till the very end - enough to return as soon as a duplicate is found. ", it is better to add a return statement after "res = True".
    Yes, I have two searches in my code, one for the input list, and the other for the dict. I think the former is necessary, and latter one is "searching & inserting" in a dict, of which the time complexity is only O(1), however the searching and inserting operation in a list is nearly O(n).

    if you have any more efficient code, please let me know.


  • 0
    C

    This one is easier to understand while complexity is O(k*n):

    def containsNearbyDuplicate(self, nums, k):
        for i in xrange(max(len(nums)-k+1, 1)):
            dic = {}
            for j in xrange(i, min(i+k+1, len(nums))):
                if nums[j] in dic:
                    return True
                dic[nums[j]] = 0
        return False

  • 0
    A

    your code is more simple and easier to understand. and it reminds me of the usage of "in".thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.