// time O(NlgK) space O(K)
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++){
            Long ceil = set.ceiling((long)nums[i]-(long)t);
            if(ceil != null && ceil <= ((long)nums[i]+(long)t)){
                return true;
            }
            set.add((long)nums[i]);
            if (set.size() == k+1){
                set.remove((long)nums[i-k]);
            }
        }
        return false;
    }
}

another way of writing it

 
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            Integer ceiling = set.ceiling(nums[i]);
            if (ceiling != null && nums[i] + t >= ceiling){
                return true;
            }
            Integer floor = set.floor(nums[i]);
            if (floor != null && floor + t >= nums[i]){
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

optimization

"""
main idea: use bucket sort. assign numbers to M bucket  based on nums[j]//(t+1) , that way different of two numbers in buckets next to each othter is at most 2*t + 1;
for twt numbers in diffrent buckets not next to each other, their difference is must bigger than t. two numbers in same bucket, their different will be at most t.
step1, if two numbers in same bucket, return true
step2, if in different bucket next to each other, check if diff <= t, if yes return true
step3 if not ,return false

Note, due to limit of |i-j| <= k, so we need to maintain a window size of k. delete expired number 
"""
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket = {}
        if t< 0 :
            return False
        for i in range(len(nums)):
        """ check can be placed in front, but need to be careful delete nums[i-k-1]since i hasnt been assesed; also check standard is i> k ; 
            if i> k : # remove the left most number
                id_del = nums[i-k-1]//(t+1)
                del bucket[id_del]
        """
            id = nums[i]//(t+1) 
            # three cases: same bucket; left bucket; right bucket
            if id in bucket:
                return True
            if id-1 in bucket and abs(bucket[id-1] - nums[i]) <= t:
                return True
            if id+1 in bucket and abs(bucket[id+1]-nums[i]) <= t :
                return True
            bucket[id] = nums[i]
            if i> k : # remove the left most number
                id_del = nums[i-k]//(t+1)
                del bucket[id_del]
        return False