# 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;
}
};