# [C++] A dummy AC solution

• I didn't know this problem can be perfectly solved by bucket search. Following is my AC solution which greedily either solve this problem in O(nt) or O(nk)

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (k<t) return nkalgo(nums, k, t);
else return ntalgo(nums, k, t);
}
bool nkalgo(vector<int>& nums, int k, int t) {
// O(nk) method
for (int offset=1;offset<=k;offset++) {
for (int i=0;i<nums.size()-offset;i++) {
long long temp= abs(((long long)nums[i])-((long long)nums[i+offset]));
if (temp<=(long long)t) return true;
}
}
return false;
}

bool ntalgo(vector<int>& nums, int k, int t) {
// O(nt) method
unordered_map<int,vector<int>> idxs;
for (int i=0;i<nums.size();i++) {
idxs[nums[i]].push_back(i);
}

for (auto it=idxs.begin();it!=idxs.end();it++) {
int val=it->first; // value now
for (int diff=-t;diff<=t;diff++) {
if ((diff>0&&val>=INT_MAX-diff)||(diff<0&&val<=INT_MIN-diff)) continue;

if (idxs.count(val+diff)>0) { // exist another matched number -> start comparing idxs
for (int i=0;i<it->second.size();i++) {
for (int j=0;j<idxs[val+diff].size();j++) {
int idxDiff=abs(it->second[i]-idxs[val+diff][j]);
if (idxDiff>0&&idxDiff<=k) return true;
}
}
}
}
}
return false;
}
};
``````

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