220 Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Solution-hashmap

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<int, int> record;
        int n = nums.size();
        for ( int i = 0; i <= n-1; i++ ) {
            if ( k >= t ) {
                for ( int j = nums[i]-t; j <= nums[i]+t; j++ ) {
                    if ( record.find(j) != record.end() and abs(record[j]-i) <= k ) return true;
                }
            }
            else {
                int j = i-1;
                while ( j >= max(0, i-k)) {
                    if ( abs(long(nums[j--]-nums[i])) <= t ) return true;
                }
            }
            record[nums[i]] = i;
        }
        return false;
    }
};

Solution-bucket

 class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size(), n_min = INT_MAX, n_max = INT_MIN;
        for ( int i = 0; i <= n-1; i++ ) {
            n_min = min(nums[i], n_min);
            n_max = max(nums[i], n_max);
        }
        if ( t < 0 ) return false;
        int m = (long(n_max) - long(n_min))/(long(t)+1) + 1;
        vector<vector<int>> record(m, vector<int>(0, 0));
        for ( int i = 0; i <= n-1; i++ ) {
            int new_index = (long(nums[i])-long(n_min))/(long(t)+1), ntmp0 = record[new_index].size();
            if ( ntmp0 != 0 and i - record[new_index][ntmp0-1] <= k) return true;
            if ( new_index >= 1 ) {
                int ntmp = record[new_index-1].size();
                for ( int j = ntmp-1; j >= 0; j-- ) {
                    if ( record[new_index-1][j] < i-k) break;
                    if ( (long(nums[i]) - long(nums[record[new_index-1][j]])) <= t ) return true;
                }
            }
            if ( new_index <= m-2 ) {
                int ntmp = record[new_index+1].size();
                for ( int j = 0; j <= ntmp-1; j++ ) {
                    if ( record[new_index+1][j] > i+k) break;
                    if ( (long(nums[record[new_index+1][j]]) - long(nums[i])) <= t ) return true;
                }
            }
            record[new_index].push_back(i);
        }
        return false;
    }
};

Notes

1. The hashmap solution uses an unordered_map to record the (number, index) pair. Whenever a new element nums[i] is examined, we search the map for all the numbers within the valid range [num[i]-t, nums[i]+t]. The time complexity is therefore $$O(N)O(t)$$. The alternative way is whenever we examine nums[i], we go through nums[i-k] to nums[i-1] to check whether there is a number in the valid range. The time complexity is therefore $$O(N)O(k)$$. Combining the two ways into one, the time complexity is reduced to $$O(N)O(min(t, k))$$.
2. The "bucket solution" also uses an unordered_map. But this time it records the (number_range, indices) pair. We use the minimum and maximum number in the array to determine the number of buckets.
   For example,

   n_min, n_max = 3, 9
   t = 2
   

   Then we want the following buckets:

   [3,4,5], [6,7,8], [9,10,11]
   

   In such a way, the numbers within the same buckets satisfies the condtion nums[i]-nums[j] <= t. An additional step is to check whether the two adjacent buckets.