O(n) using C++ deques


  • -2
    C
    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)


  • 0
    O

    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


  • 0

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


  • 0
    X
    This post is deleted!

  • 0
    C

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


Log in to reply
 

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