# C++ n*log(k) solution, explained in the comments

• ## Explained in comments.

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int size = nums.size();
if (k >= size)
k = size - 1;
if (k <= 0)
return false;
***// a slide window containing k + 1 item***
multiset<long long> window;

// initilize window and check first window k * log(k)
for (int i = 0; i <= k; i++)
{
window.insert(nums[i]);
}
auto pre = window.begin();
auto cur = ++window.begin();
while (cur != window.end())
{
if (*cur - *pre <= t)
return true;
pre = cur;
++cur;
}

***// slide the window one by one. The window is guaranteed that ele is at least t far away from its neighbors***
for (int i = k + 1; i < size; i++)
{
window.erase(window.find(nums[i - k - 1]));

int curValue = nums[i];
if (window.find(curValue) != window.end())
return true;
auto up = window.upper_bound(curValue); ***// curValue will be inserted into some interval, compare its right and left side***
if (up != window.end() && *up - curValue <= t)
return true;
if (up != window.begin())
{
--up;
if (curValue - *up <= t)
return true;
}

window.insert(curValue);
}

return false;
}
};``````

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