C++ using set (less 10 lines), with simple explanation.


  • 105
    L
     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int> window; // set is ordered automatically 
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
            // |x - nums[i]| <= t  ==> -t <= x - nums[i] <= t;
            auto pos = window.lower_bound(nums[i] - t); // x-nums[i] >= -t ==> x >= nums[i]-t 
            // x - nums[i] <= t ==> |x - nums[i]| <= t    
            if (pos != window.end() && *pos - nums[i] <= t) return true;
            window.insert(nums[i]);
        }
        return false;
    }

  • 0
    S

    Hey guys, if you change "*pos <= (long)nums[i] + (long)t" to "*pos - nums[i] <= t". It is not necessary to convert them to long integer.


  • 0
    L

    Yeap, you are right, I have updated the code according to your suggestion.


  • 0
    P

    It's better if you implement the binary search tree yourself!


  • 4
    M

    Nice solution! The time complexity is O(n*log(k)), right?


  • 0
    M

    what's the time complexity? each erase/insert is nlog(n). So the complexity is klog(k)*n?


  • 0
    W

    Each insert/erase causes log(k)


  • 1
    L

    I think it should be O(n*log(k)), since insert, erase and lower_bound causes log(k).


  • 4
    A

    My solution is similar but I feel it's easier to understand. Basically I check the biggest element smaller than target and smallest element bigger than target in the window to see if any one of them is in the range.

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
      set<long long> s;
      if(k==0) return false;
    	for(int i=0; i<nums.size(); i++){
    		long long val = nums[i];
    		if(!s.empty()){
    		    
    			if(s.size()==k+1)	s.erase(nums[i-k-1]);
    			auto higher = s.lower_bound(val);
                //higher points to smallest element bigger or equal to val
    			if(higher!=s.end()&&(*higher-val<=t)) return true;
    			if(higher!=s.begin()) { 
    				higher--;
                    //now higher should point to biggest element smaller than val
    				auto low = higher;
    				if(low!=s.end()&&((val-*low)<=t))	return true;
    			}
    		}
    		s.insert(val);
    	}
    	return false;
    }
    

    I feel both mine and the one posted by OP doesn't handle cases where there are duplicate values in the window.

    ------10 months later-----------

    Now I think OP's solution is the best and duplication is just fine. :)


  • 2
    G

    should you use a multiset?


  • 0
    D

    It is not needed.
    Suppose nums[i] == nums[j] (where i - j <= k), so after pos = window.lower_bound() we receive pointer on nums[j] or for other element that satisfies *pos - nums[i] <= t, that means that we could reach at most two duplicates in interval.


  • 0
    C

    nice solution but really difficult to understand


  • 0
    H

    search for nums[i] - t is tricky!


  • 1
    H

    but still, your code is vulnerable to overflow.


  • 0
    Z

    c++, O(n(logk)), use stl set, for each nums[i], we try to find prev smaller and next larger element of nums[i] from elements nums[i - k, i - 1]

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if(nums.size() <= 1 || k <= 0 || t < 0){
                return false;
            }
            multiset<long long> s;
            for(int i = 0; i < nums.size(); ++i){
                if(i - k - 1 >= 0){
                    s.erase(nums[i - k - 1]);
                }
                
                s.insert(nums[i]);
                auto it = s.find(nums[i]);
                if(it != s.begin()){
                    --it;
                    if(abs(*it - nums[i]) <= t){
                        return true;
                    }
                    ++it;
                }
                if(it != s.end()){
                    ++it;
                    if(it != s.end() && abs(*it - nums[i]) <= t){
                        return true;
                    }
                }
            }
            
            return false;
        }

  • 0
    A

    seems don't need to check low == s.end()


  • 0
    P

    can you explain why vulnerable to overflow?


  • 0
    This post is deleted!

  • 10

    Nice solution, but it will occur overflow in the following case due to "nums[i] - t".
    [-2147483647, -2147483648]
    1
    1
    The expected answer is True, but yours returns False.


  • 0
    K

    I'm confused about that why don't you execute insert sentence before lower_bound check sentences? Could you explain detailly? Thanks so much.


Log in to reply
 

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