# clean O(n) bucket solution, C++

• The basic idea is to put each number into corresponding bucket, then check those two constraints. The bucket size should be t+1(consider edge case t = 0). Each bucket only stores the largest index of numbers in it.

For each number,

1. find the index of bucket it belongs to
2. check those two constraints with the current bucket and adjacent buckets.

Time : O(n)
space : O(t)

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, long t) {
if (nums.size() < 2 || t < 0 || k < 0) return false;
int minx = INT_MAX, maxx = INT_MIN;
//find the minimum and maximum to determine the number of buckets
for (auto & i : nums) {
minx = min(minx, i);
maxx = max(maxx, i);
}
int n = ((long)maxx - (long)minx) / (t + 1) + 1;
//initialize by -(k + 1)
vector<int> buckets(n, -(k + 1));
for (int i = 0, j; i < nums.size(); i++) {
//get the index of bucket
j = ((long)nums[i] - (long)minx) / (t + 1);
//check the two constraints
if ((i - buckets[j] <= k) || (j && i - buckets[j - 1] <= k && (long)nums[i] - (long)nums[buckets[j - 1]] <= t) || (j < n - 1 && i - buckets[j + 1] <= k && (long)nums[buckets[j + 1]] - (long)nums[i] <= t))
return true;
buckets[j] = i;
}
return false;
}
};
``````

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