O(n) using C++ deques

• ``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
deque<int> maxq, minq; // priority queue with max length k
for(int i = 0; i < nums.size(); ++i) {
while(!maxq.empty() && i - maxq.front() > k) maxq.pop_front(); // The greatest must also be the oldest. Otherwise it would have been popped from back
if(!maxq.empty() && abs((long long)nums[i] - nums[maxq.front()]) <= t) return true;

while(!minq.empty() && i - minq.front() > k) minq.pop_front(); // Pop the oldest
if(!minq.empty() && abs((long long)nums[i] - nums[minq.front()]) <= t) return true;

while(!maxq.empty() && nums[maxq.back()] <= nums[i])  maxq.pop_back();
maxq.push_back(i);
while(!minq.empty() && nums[minq.back()] >= nums[i]) minq.pop_back();
minq.push_back(i);
}
return false;
}
};
``````

I use deque to maintain an increasing or decreasing queue whose maximum size is k. When the queue is too long, I remove the oldest element from the left. The increasing/decreasing characteristic assures that the left-most element must be the oldest. Otherwise it would have been popped from back.

Each nums[i] is compared against the max/min of the queue (i.e., the max/min of the last k elements)

Asymptotically each element is only pushed to or popped from the deque once, so the overall runtime is O(n)

• Spent far too long looking at this, trying to understand the logic behind it. I don't think it is 100% correct, say on teh following:

nums = [4, 1, 6, 3]
k = 100
t = 1

Should return true because 4 and 3 , however when I run it returns false. Not sure how to fix the algorithm, or if fixable
PS Chance have misunderstood question, please correct me if so

• Thanks for your test case, I've just added this test case.

• This post is deleted!

• You are right. It does not pass with your test case.

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