## Approach 1: Ordered Set

• Time:O(n\log k)
• Space:O(k)

## C++

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long> window;

for (int i = 0; i < nums.size(); ++i) {
const auto it = window.lower_bound(static_cast<long>(nums[i]) - t);
if (it != cend(window) && *it - nums[i] <= t)
return true;
window.insert(nums[i]);
if (i >= k)
window.erase(nums[i - k]);
}

return false;
}
};


## JAVA

class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Long> set = new TreeSet<>();

for (int i = 0; i < nums.length; ++i) {
final long num = (long) nums[i];
final Long ceiling = set.ceiling(num); // the smallest num >= nums[i]
if (ceiling != null && ceiling - num <= t)
return true;
final Long floor = set.floor(num); // the largest num <= nums[i]
if (floor != null && num - floor <= t)
return true;
if (i >= k)
set.remove((long) nums[i - k]);
}

return false;
}
}


## Approach 2: Bucket

• Time:O(n)
• Space:O((\max(nums) - \min(nums)) / t) \to O(k)

## C++

class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.empty() || k <= 0 || t < 0)
return false;

const long min = *min_element(begin(nums), end(nums));
const long diff = t + 1L;  // in case of t = 0
// use long because corner case INT_MAX - (-1) will overflow
unordered_map<long, long> bucket;

for (int i = 0; i < nums.size(); ++i) {
const long num = nums[i];
const long key = getKey(num, min, diff);
if (bucket.count(key))  // current bucket
return true;
if (bucket.count(key - 1) &&
num - bucket[key - 1] < diff)  // left adjacent bucket
return true;
if (bucket.count(key + 1) &&
bucket[key + 1] - num < diff)  // right adjacent bucket
return true;
bucket[key] = num;
if (i >= k)
bucket.erase(getKey(nums[i - k], min, diff));
}

return false;
}

private:
int getKey(long num, long min, long diff) {
return (num - min) / diff;
}
};


## JAVA

class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length == 0 || k <= 0 || t < 0)
return false;

final long min = Arrays.stream(nums).min().getAsInt();
final long diff = (long) t + 1; // in case of t = 0
// use Long because of corner case Integer.MAX_VALUE - (-1) will overflow
HashMap<Long, Long> bucket = new HashMap<>();

for (int i = 0; i < nums.length; ++i) {
final long num = (long) nums[i];
final long key = getKey(nums[i], min, diff);
if (bucket.containsKey(key)) // current bucket
return true;
if (bucket.containsKey(key - 1) && num - bucket.get(key - 1) < diff) // left adjacent bucket
return true;
if (bucket.containsKey(key + 1) && bucket.get(key + 1) - num < diff) // right adjacent bucket
return true;
bucket.put(key, num);
if (i >= k)
bucket.remove(getKey(nums[i - k], min, diff));
}

return false;
}

private long getKey(int num, long min, long diff) {
return ((long) num - min) / diff;
}
}


## Python

class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
if not nums or k <= 0 or t < 0:
return False

mini = min(nums)
diff = t + 1
bucket = {}

def getKey(num: int) -> int:
return (num - mini) // diff

for i, num in enumerate(nums):
key = getKey(num)
if key in bucket:  # current bucket
return True