# Contains Duplicate III

## Solution

#### TreeSet (Binary Search Tree)

``````public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
// Find the successor of current element
Integer s = set.ceiling(nums[i]);
if (s != null && s <= nums[i] + t) return true;

// Find the predecessor of current element
Integer g = set.floor(nums[i]);
if (g != null && nums[i] <= g + t) return true;

if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
``````

BST solution is incorrect in following case:

``````[-1, 2147483647]
1
2147483647
``````

#### Using Buckets

20 ms, faster than 89.87%

Inspired by bucket sort, we can achieve linear time complexity in our problem using buckets as window.

buckets的元素的数目保持在k个，相当于保持滑动窗口。

`Map<Long, Long> buckets = new HashMap<>();`

buckets存入bucket id到nums[i]的映射

`((long) num - (long) min) / diff;`

``````class Solution {
private long getBucketIndex(int num, int t, int min, long diff) {
return ((long) num - (long) min) / diff;
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0 || k < 0 || t < 0) {
return false;
}
Map<Long, Long> buckets = new HashMap<>();

int min = Integer.MAX_VALUE;
for (int num : nums) {
min = Math.min(num, min);
}
long diff = (long) t + 1;

for (int i = 0; i < nums.length; i++) {
long index = getBucketIndex(nums[i], t, min, diff);

if (buckets.containsKey(index)) {
return true;
}

if (buckets.containsKey(index - 1) && Math.abs(nums[i] - buckets.get(index - 1)) < diff) {
return true;
}

if (buckets.containsKey(index + 1) && Math.abs(nums[i] - buckets.get(index + 1)) < diff) {
return true;
}

buckets.put(index, (long) nums[i]);
if (i >= k) {
buckets.remove(getBucketIndex(nums[i - k], t, min, diff));
}
}
return false;
}
}
``````

https://www.laioffer.com/en/videos/2018-07-23-220-contains-duplicate-3/