220. Contains Duplicate III

Problem Link

Tutorial

We can use multiset and binary search. But remember to user the member function lower bound instead of the independent function lower bound. The best solution is bucketing with O(n) complexity.

We slide a window of length k. We just bucket all the nums by dividing t + 1. So each time if the new element falls in the same bucket with another value means true. If not, check its neighbour bucket's value. If satisfy the limits return true. Remember that at most one element in one neighbour bucket, otherwise it would return true earlier.

Solution

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
    if t < 0:
        return False
    if k < 0:
        return False
    n = len(nums)
    my_dict = {}
    for i in range(n):
        temp = nums[i] / (t + 1)
        if temp in my_dict:
            return True
        if temp - 1 in my_dict and abs(nums[i] - my_dict[temp - 1]) <= t:
            return True
        if temp + 1 in my_dict and abs(nums[i] - my_dict[temp + 1]) <= t:
            return True
        my_dict[temp] = nums[i]
        if i >= k:
            my_dict.pop(nums[i - k] / (t + 1))
    return False