Leetcode 220


  Posted on 10 Mar 2017
bucketing


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