# 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 absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

# Solution

Approach 1: Maintain an ordered window (length k+1) of nums, use logN time to add and kick out numbers. In C++: set and lower bound. Time: O(Nlogk).

Approach 2: put numbers into buckets (each bucket has range 0 to t inclusive), so the presence of a bucket means a match exists. Evict stale buckets. Time: O(N).

# Code (Python)

Approach 1:

    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        # idea: maintain a sorted window (length k+1) of nums, use binary search to add and kick out numbers. O(nlogk) time.
        k += 1
        window = sorted(nums[:k])
        for i in range(1, len(window)):
            if abs(window[i] - window[i-1]) <= t:
                return True
        right = k
        while right < len(nums):
            i = bisect.bisect_left(window, nums[right - k])
            window = window[:i] + window[i + 1:]
            j = bisect.bisect_left(window, nums[right])
            if j - 1 >= 0 and abs(nums[right] - window[j - 1]) <= t:
                return True
            if j < len(window) and abs(nums[right] - window[j]) <= t:
                return True
            window = window[:j] + [nums[right]] + window[j:]
            right += 1
        
        return False

Approach 2:

    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        # idea: put numbers into buckets (each bucket has range 0 to t inclusive), so the presence of a bucket means a match exists. Evict stale buckets.
        if t < 0:
            return False
        buckets = {}
        for i, num in enumerate(nums):
            bucket = num // (t + 1) # t + 1 maps num % (t+1) in ranges 0 to t inclusive
            # need to check the neighboring buckets as well
            if bucket in buckets or (bucket - 1 in buckets and abs(num - buckets[bucket - 1]) <= t) or (bucket + 1 in buckets and abs(num - buckets[bucket + 1]) <= t):
                return True
            buckets[bucket] = num
            if i >= k:
                del buckets[nums[i - k] // (t + 1)]

# Code (C++)

Approach 1:

// Set.
// x - y <= t && y - x <= t  -->  x <= y + t && x >= y - t
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> s;
        for (int i = 0; i < nums.size(); ++i)
        {
            set<long>::iterator it = s.lower_bound((long)nums[i] - (long)t);
            if (it != s.end() && *it <= (long)nums[i] + (long)t)
                return true;
            s.insert(nums[i]);
            if (i + 1 > k)
                s.erase(nums[i-k]);
        }
        return false;
    }
};