c++ solution using bucket, beats 99.6%

• Inspired by @maruchan76 https://discuss.leetcode.com/topic/29477/why-no-one-posted-o-n-solution-in-c-using-bucket-sort, but use a array (buckets) to store the indices of numbers in vector "nums" without using unordered_map. Use type long long to prevent overflow.

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (k < 1 || t < 0) return false;
int min_num = INT_MAX;
int max_num = INT_MIN;
for (auto& num: nums) {
min_num = std::min(min_num, num);
max_num = std::max(max_num, num);
}
long long bucket_width = static_cast<long long>(t) + 1;
int size = (static_cast<long long>(max_num) - static_cast<long long>(min_num)) / bucket_width + 1;
int* bucket = new int[size];
memset(bucket, -1, sizeof(int) * size);
for (int i = 0; i < nums.size(); i++) {
int bucket_idx = (static_cast<long long>(nums[i])-min_num) / bucket_width;
if (bucket[bucket_idx] >= 0)
return true;
bucket[bucket_idx] = i;
if (bucket_idx >= 1) {
int j = bucket[bucket_idx-1];
if (j >= 0 && abs(static_cast<long long>(nums[i]) - nums[j]) <= t)
return true;
}
if (bucket_idx < size-1) {
int l = bucket[bucket_idx+1];
if (l >= 0 && abs(static_cast<long long>(nums[i]) - nums[l]) <= t)
return true;
}
if (i >= k) {
bucket[(nums[i-k] - min_num) / bucket_width] = -1;
}
}
return false;
}
};
``````

• Don't know why nobody votes this. This definitely the fastest C++ solution.

• Here's java version. cpp type casting is awesome, while java's :-(

I'm impressed by your code `static_cast<long long>(t) + 1`, and the type casting is just precise.

Well there's an edge case that can't be handle by the Java. If the `min = Integer.MIN_VALUE, max = Integer.MAX_VALUE;` and `t = 1`, size will still overflow, which will be 2^31 instead of 2^31-1.

Another reason is that in Java, only `int` type can be used to index on an array, so the `size` can't be long type. array size limit. However, CPP has no hard limitation on the array size.

``````public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0)
return false;

long range;
long max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int num : nums) {
max = max > num ? max : num;
min = min < num ? min : num;
}
range = max - min + 1;
long bucket_with = ((long) t) + 1;
int size = (int) (range / bucket_with + 1);
int[] buckets = new int[size];
Arrays.fill(buckets, -1);

for (int i = 0; i < nums.length; i++) {
int bucket_idx = (int) ((((long) nums[i]) - min + 1) / bucket_with );
if (buckets[bucket_idx] >= 0) {
return true;
}
buckets[bucket_idx] = i;

if (bucket_idx > 0) {
int j = buckets[bucket_idx-1];
if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
return true;
}
}

if (bucket_idx < size-1) {
int j = buckets[bucket_idx + 1];
if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
return true;
}
}

if (i >= k) {
buckets[(int) ((((long) nums[i-k]) - min + 1) / bucket_with )] = -1;
}
}

return false;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.