Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.


Example 1:


Input: nums = [1,2,3,1], k = 3, t = 0
Output: true



Example 2:


Input: nums = [1,0,1,1], k = 1, t = 2
Output: true



Example 3:


Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Difficulty: interview

Starter code:

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        

Solutions:
class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if len(nums) < 2 or k <= 0 or t < 0: return False
         if t == 0:
             visited = set()
             for i, n in enumerate(nums):
                 if n in visited: return True
                 visited.add(n)
                 if i >= k: visited.remove(nums[i-k])
             return False
         bucket = {}
         for i, n in enumerate(nums):
             b = n // t
             if b in bucket: return True
             if b+1 in bucket and abs(bucket[b+1]-n) <= t: return True
             if b-1 in bucket and abs(bucket[b-1]-n) <= t: return True
             bucket[b] = n
             if i >= k: del bucket[nums[i-k]//t]
         return False

class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         nums2 = [(n, i) for i, n in enumerate(nums)]
         nums2 = sorted(nums2)
         print(nums2)
         for i in range(1, len(nums2)):
             j = i-1
             a, n = nums2[j]
             b, m = nums2[i]
             while abs(a-b) <= t:
                 if abs(n-m) <= k:
                     return True
                 j -= 1
                 if j < 0:
                     break
                 a, n = nums2[j]
 
         return False
             


class Solution(object):
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if k < 1 or t < 0:
             return False
         import sys
 
         bh = {}
         # To prevent 0 as a divisor
         w = t+1
         for i in range(len(nums)):
             n_i = nums[i]
             n_i_w = n_i // w
             if n_i_w in bh:
                 return True
             if n_i_w-1 in bh and abs(n_i - bh[n_i_w-1]) < w:
                 return True
             if n_i_w+1 in bh and abs(n_i - bh[n_i_w+1]) < w:
                 return True
             bh[n_i_w] = nums[i]
             if len(bh) > k:
                 del bh[(nums[i - k]) // w]
         return False


class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         
         if t<0:
             return False
         
         w = t+1
         d = {}
         
         for i in range(0, len(nums)):
             m = nums[i]//w
             #print(m,d)
             if m in d:
                 return True
             if m-1 in d and abs(nums[i]-d[m-1])<=t:
                 return True
             if m+1 in d and abs(nums[i]-d[m+1])<=t:
                 return True
             d[m] = nums[i]
             if i>=k:
                 del d[nums[i-k]//w]
                 
         return False


class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if t < 0: return False
         n = len(nums)
         buckets = {}
         w = t + 1
         for i in range(n):
             bucket_num = nums[i] // w
             if bucket_num in buckets:
                 return True
             if bucket_num - 1 in buckets and abs(nums[i] - buckets[bucket_num - 1]) < w:
                 return True
             if bucket_num + 1 in buckets and abs(nums[i] - buckets[bucket_num + 1]) < w:
                 return True
             buckets[bucket_num] = nums[i]
             if i >= k: del buckets[nums[i-k]//w]
         return False


class Solution:
     def equalSol(self, nums, k):
         if k == 0:
             return False
         d = {}
         for i in range(len(nums)):
             if nums[i] in d.keys() and abs(i - d[nums[i]]) <= k:
                 return True
             else:
                 d[nums[i]] = i
         return False
     
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if k == 0:
             return False
         if t == 0:
             return self.equalSol(nums, k)
         for i in range(len(nums)):
             for j in range(1,(k+1)):
                 if (i + j) < len(nums) and abs(nums[i] - nums[i+j]) <= t:
                     return True
                 if (i - j) >= 0 and abs(nums[i] - nums[i-j]) <=t:
                     return True
         return False

class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         buckets = {}
         for i, v in enumerate(nums):
             bucket_num, offset = (v//t, 1) if t else (v, 0)
             for idx in range(bucket_num - offset, bucket_num + offset + 1):
                 if idx in buckets and abs(buckets[idx] - nums[i]) <= t:
                     return True
         
             buckets[bucket_num] = nums[i]
             if len(buckets) > k:
                 del buckets[nums[i-k] // t if t else nums[i-k]]
         
         return False


class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if t < 0: return False
         n = len(nums)
         buckets = {}
         w = t + 1
         for i in range(n):
             bucket_num = nums[i] // w
             if bucket_num in buckets:
                 return True
             if bucket_num - 1 in buckets and abs(nums[i] - buckets[bucket_num - 1]) < w:
                 return True
             if bucket_num + 1 in buckets and abs(nums[i] - buckets[bucket_num + 1]) < w:
                 return True
             buckets[bucket_num] = nums[i]
             if i >= k: del buckets[nums[i-k]//w]
         return False


class Solution:
     # @param {integer[]} nums
     # @param {integer} k
     # @param {integer} t
     # @return {boolean}
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         if len(nums) == 0 or len(nums) == 1 or k < 1 or t < 0:
             return False
         d = collections.OrderedDict()
         for i in nums:
             key = i if not t else i // t
             for j in (d.get(key - 1), d.get(key), d.get(key + 1)):
                 if j != None and abs(j - i) <= t:
                     return True
             if len(d) == k:
                 d.popitem(False)
             d[key] = i
             
         return False

class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if k < 1 or t < 0:
             return False
         m = len(nums)
         if m == 0:
             return False
         
         
         buckets = {}
         _min = 0
         for i in range(m):
             num = nums[i] - _min
             bucket = num // (t + 1)
             flag = bucket in buckets \
                 or (bucket - 1 in buckets and abs(buckets[bucket - 1] - num) <= t) \
                 or (bucket + 1 in buckets and abs(buckets[bucket + 1] - num) <= t)
                 
             if flag:
                 return True
             if len(buckets) >= k:
                 del buckets[(nums[i - k] - _min) // (t + 1)]
             
             buckets[bucket] = num
         return False

class Solution:
     def containsNearbyAlmostDuplicate(self, nums, k, t):
         """
         :type nums: List[int]
         :type k: int
         :type t: int
         :rtype: bool
         """
         if t < 0:
             return False
         d = {}
         w = t + 1
         
         for i in range(len(nums)):
             b = nums[i] // w
             if b in d:
                 return True
             if b - 1 in d and abs(nums[i] - d[b - 1]) < w:
                 return True
             if b + 1 in d and abs(nums[i] - d[b + 1]) < w:
                 return True
             d[b] = nums[i]
             if i >= k:
                 del d[nums[i - k] // w]
         
         return False