# C++ solution without using set::lower_bound

• Hi all,

This is my first time to post code in this Discuss forum.

The idea is basically heritage from Contains-Duplicate-ii, by offering another way to find duplicates.

The total time complexity is O(N * min(k, 2log(k)(t + 1)))**, where N is the length of the array.

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.size() < 2)
return false;

if (k < 0 || t < 0)
return false;

return containsNearbyAlmostDuplicateCore(nums, (long long)k, (long long)t);
}

private:
bool containsNearbyAlmostDuplicateCore(vector<int>& nums, long long k, long long t) {
//Record the latest (k+1) numbers
set<int> latestNums;
latestNums.insert(nums[0]);

for (int i = 1; i < nums.size(); i++) {
if (i > k) {
latestNums.erase(nums[i - k - 1]);
}

if (k == 1 || k < 2 * log(k) * (t + 1)) { //If t is int, 2 * t may overflow, so convert it to long long
for (auto iter = latestNums.begin(); iter != latestNums.end(); iter++) {
if (abs((long long)*iter - nums[i]) <= t) {
return true;
}
}
} else {
for (int j = 0; j <= t; j++) {
if (latestNums.find(nums[i] + j) != latestNums.end() || latestNums.find(nums[i] - j) != latestNums.end()) {
return true;
}
}
}

latestNums.insert(nums[i]);
}

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

Note:

L 24~36:

k and t may be very big and cause TLE. Need to choose which way to compare according to k and t's value.

Since L31~36's time complexity is 2 * log(k) * (t + 1), when k == 1 (since log(1) == 0) or k <= 2 * log(k) * (t + 1), try to find duplicate by numbers' indices. Else, try by difference in values.

L10, L26:

Watch out for overflows.

I know this is a bit hacky but it works without dependence of set::lower_bound function.

Any thoughts?

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