text: """
  https://leetcode.com/problems/contains-duplicate-iii/
  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
  """
  
  # time complexity: O(n), space complexity: O(k)
  # this solution is provided by @jac24 in the discussion area.
  # the main idea is to scale down all the numbers by t -> scaledDownNumber, then only search from scaleDownNumber-1 to scaledDown+1 to see if there is any number in the bucket and if the number satisfy the requirement. We need to make the bucket number fixed length, length = k so as long as we find some number in the buckets, that will be the solution.
  
  class Solution:
      def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
          # Bucket sort. Each bucket has size of t. For each number, the possible
          # candidate can only be in the same bucket or the two buckets besides.
          # Keep as many as k buckets to ensure that the difference is at most k.
          buckets = {}
          for i, v in enumerate(nums):
              # t == 0 is a special case where we only have to check the bucket
              # that v is in.
              bucketNum, offset = (v // t, 1) if t else (v, 0)
              for idx in range(bucketNum - offset, bucketNum + offset + 1):
                  if idx in buckets and abs(buckets[idx] - nums[i]) <= t:
                      return True
  
              buckets[bucketNum] = nums[i]
              if len(buckets) > k:
                  # Remove the bucket which is too far away. Beware of zero t.
                  del buckets[nums[i - k] // t if t else nums[i - k]]
  
          return False
  