Problem Link

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that

• abs(nums[i] - nums[j]) <= t and
• abs(i - j) <= k.

Solution

Bucket size: t + 1

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        d = dict()
        w = t + 1
        for i in range(len(nums)):
            id = self.getID(nums[i], w)
            if id in d:
                return True
            if id-1 in d and abs(nums[i] - d[id-1]) <= t:
                return True
            if id+1 in d and abs(nums[i] - d[id+1]) <= t:
                return True
            d[id] = nums[i]
            if i >= k:
                removeID = self.getID(nums[i-k], w)
                del d[removeID]

    def getID(self, n, w) -> int:
        return n // w