Python concise solution with dictionary.


  • 36
    C
    def containsNearbyDuplicate(self, nums, k):
        dic = {}
        for i, v in enumerate(nums):
            if v in dic and i - dic[v] <= k:
                return True
            dic[v] = i
        return False

  • 0
    N

    I keep a window of size k, but get "Time Limit Exceeded":

    def contains_near_by_duplicate1(self, nums, k):
        if not nums or k <= 0:
            return False
    
        num_dict = {}
        for index, value in enumerate(nums):
            if value in num_dict.values():
                return True
            else:
                num_dict[index] = value
    
            if index > k:
                del num_dict[index-k-1]
    
        return False

  • 0
    C

    what's the time complexity of enumerate? O(n)?


  • 2
    I

    @nkcoder
    The reason that you're getting TLE is because you're searching for a value in a list in the line: if value in num_dict.values() which takes O(n). OP avoids that by using the value as a key of the dictionary. Thus, the value can be searched in the dictionary in O(1) time.


  • 0
    C
            d = {}
            for i,item in enumerate(nums):
                try:
                    d[item].append(i)
                    if (d[item][-1]-d[item][-2])<=k:
                        return True
                except:
                    d[item] = [i]
            return False
    

  • 0
    A

    @ikelber Can I ask you a stupid question? what is OP??
    And I think the original solution also got TLE


  • 0
    J

    I used this method to keep a k length window, but meet Time Limited Exceeded problem, someone can explain that? Thanks.

        if len(nums)==0 or k<=0:
            return False      
        dic = {}
        for index,value in enumerate(nums):
            if index>k:
                del dic[index-k-1]
            if value in dic.values():
                return True
            else:
                dic[index] = value               
        return False

  • 0
    J

    @nkcoder I tried your method but meet TLE problem. Also you should move the update of dictionary to the first part of for loop.


Log in to reply
 

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