Naive Python without sorting...


  • 1
    Z

    Consider iterate in a range of min(2t, len(dict)).

    Time complexity ~O(min(t,n)*n)

    def containsNearbyAlmostDuplicate(self, nums, k, t):
        numDict = {}
        for index, num in enumerate(nums):
            if len(numDict) > 2*t:
                for i in range(num-t, num+t+1):
                    if i in numDict and index-numDict[i] <= k:
                            return True
            else:
                for i in numDict:
                    if abs(num-i) <= t and index-numDict[i] <= k:
                        return True
            numDict[num] = index
        return False

  • 0
    Z

    After a quick review of bucket sort I think bucket sort may be a headache for this question, especially the potential large space complexity.

    Any one can suggest a leetcode question that really needs bucket sort? Thanks.


  • 0
    Z

    if "i = -1000, num = 2147483648 " , your "abs(num-i) will overflow"


Log in to reply
 

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