# Finally AC, C++ 16ms using map, O(nlogn) with explanation

1. Using a map to store the numbers, takes `O(nlogn)`.
key(nums[i]) - value(index), value is a `vector<int>` since duplicate numbers can have multiple indices.
2. If array contains duplicate numbers and the absolute difference between their indices <=k, return `true`.
3. Since map is already sorted, we only need to check the interval`(map[i], map[i+t])`, which could be seen as constant time `O(1)` depends on `t` and array itself.
``````    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<int,vector<int>>m;
for(int i=0;i<nums.size();i++) m[nums[i]].push_back(i);
for(map<int,vector<int>>::iterator it1=m.begin();it1!=m.end();it1++){
if(it1->second.size()>1 && minDiff(it1->second)<=k && t>=0) return true;
map<int,vector<int>>::iterator it2=it1;
it2++;
for(;it2!=m.end();it2++){
int diff=it2->first-it1->first;
if(diff>t) break;
if(it2->first>0 && it1->first<0 && diff<it2->first) continue; //check overflow
if(it2->first<0 && it1->first>0 && diff>0) continue; //check overflow
if(diff<=t && minDiff(it1->second,it2->second)<=k) return true;
}
}
return false;
}

int minDiff(vector<int>& v1, vector<int>& v2){
int minD=INT_MAX;
for(int i=0;i<v1.size();i++)
for(int j=0;j<v2.size();j++) minD=min(minD,abs(v1[i]-v2[j]));
return minD;
}

int minDiff(vector<int>& v){
int minD=INT_MAX;
for(int i=0;i<v.size();i++)
for(int j=i+1;j<v.size();j++) minD=min(minD,abs(v[i]-v[j]));
return minD;
}
``````

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