Question

• https://leetcode.com/problems/contains-duplicate-iii/

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Approach

• Naiive moving window, gives TLE

• The following answer is based on buckets and the time complexity is O(n).

  The basic idea is to use a sliding window whose width is k. Our attention will be constrained in this window so that the difference between i and j (indices) in this window can not be greater than k. And we check whether there are two numbers in this window with difference at most t. If there are such numbers, then we’re done. Otherwise, our window will move forward one step, and we’ll check again.

  Now the real question is how do we check if there are two such numbers in the window. Of course we can use brutal force, which will be O(K^2), then the whole algorithm will be O(n * K^2). If K is not large, we can accept this.

  However, by using buckets, we can do far better!

  Whenever we encounter a number in the window, we divide it by (t+1). Suppose the result is B, we then put the number into bucket[B].

  If t = 3, then numbers 0, 1, 2, 3 will all be put into bucket[0], numbers 4, 5, 6, 7 will be put into bucket[1] and 8, 9, 10, 11 will be put into bucket[2] and so on. We have guaranteed all numbers in one bucket will have differences not larger than t. And there is still one thing: 4 - 2 = 2 < 3 and they are in different buckets. Yes, some numbers with differences less than t may be put into different buckets. In such cases, however, they can only be in neighboring buckets.

  Below is an example:

  nums = [1, 5, 17, 6, 8], t = 2, k = 5

  (We don’t have to worry about k now since it’s the same as the length of nums.)

  Since t = 2, so whenever we encounter a number in the list, we divide it by t+1 (integer divide is used) and put it in corresponding bucket.

  1 / 3 = 0 –> We put 1 in bucket[0]

  5 / 3 = 1 –> We put 5 in bucket[1]

  Since there may be elements in buckets neighboring bucket[1] satisfying the requirements, we need to check this. bucket[0] has number 1, but 5 - 1 > 3 and there’s no bucket[2] yet, so we carry on.

  17 / 3 = 5 –> We put 17 in bucket[5]

  There’s no bucket[4] or bucket[6], so we carry on.

  6 / 3 = 2 –> We put 6 in bucket[2]

  We have to check number in bucket[1]:

  5 - 6

  = 1 < 2 so there are such numbers and we return True.

  If we continue to put 8 in bucket[2] we’ll find there already is an element in it, which is 6. Since all elements in one bucket have differences not larger that t, we are done.

  So to check if there are two numbers with differences less than t, we put every number we encounter in a bucket. If there is already an element in that bucket, then we’re done. Otherwise, we check if neighboring buckets have element satisfying the requirement, if there isn’t, we continue to put numbers into bucket.

  We’re almost finished. Now we need to consider the window width k. After putting all k numbers into buckets, if we haven’t find two such numbers, we need to move the window one step forward. That is to say, to delete the leftmost number and its corresponding bucket and add a new number into its bucket. If its bucket has already been taken, then we’re done. Otherwise we check its neighboring buckets, if it has any.

Solution

#define ll long long
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty() || k<0 || t<0) return false;
        int n = nums.size();
        unordered_map<ll,ll> u;
        for(int i=0;i<n;i++)
        {
            int b = floor(1.0*nums[i]/((ll)t+1));
            if(u.count(b)) return true;
            else if(u.count(b+1) && (u[b+1]-nums[i]<=t)) return true;
            else if(u.count(b-1) && (-u[b-1]+nums[i]<=t)) return true;
            else
            {
                u[b]=nums[i];
                if(size(u)>k)
                {
                    int new_b = floor(1.0*nums[i-k]/((ll)t+1));
                    u.erase(new_b);
                }
            }
        }
        return false;
    }
};