AC python code using window and bucketing


  • 6
    X
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @param {integer} t
        # @return {boolean}
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            if k <= 0 or t < 0:
                return False
            numsDict = {}
            for i in range(len(nums)):
                bucket = nums[i]/(t+1)
                for key in [bucket-1, bucket, bucket+1]:
                    if key in numsDict and abs(numsDict[key] - nums[i]) <= t:
                        return True
                numsDict[bucket] = nums[i]
                if i+1 > k:
                    pop_key = nums[i-k]/(t+1)
                    numsDict.pop(pop_key)
            return False
    

    Basically, I kept a window of size k and put all integers in that window into buckets. The index of the bucket is integer mod (t+1), as to avoid zeroDivisionError when t = 0. The runtime should be O(n) for this algorithm.


  • 0
    S
    This post is deleted!

Log in to reply
 

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