Python concise solution with dictionary.


  • 40
    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.


  • 0
    W
    This post is deleted!

Log in to reply
 

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