Leetcode 220: Contains Duplicate III

https://leetcode.com/problems/contains-duplicate-iii/

Code

import sys

class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if not nums or k <=0 or t<0:
            return False

        def tran_num(org_num):
            return org_num + sys.maxint     
            
        def to_bucket(num_tran):
            return num_tran / (t+1)

        bucket_dict = {}
        for idx, num in enumerate(nums):
            num_tran = tran_num(num)
            bucket = to_bucket(num_tran)        
            
            if bucket_dict.get(bucket) or \
                bucket_dict.get(bucket+1, num_tran+t+1) - num_tran <=t or \
                num_tran - bucket_dict.get(bucket-1, num_tran-t-1) <=t:
                return True
                
            if idx >=k:
                old_bucket = to_bucket(tran_num(nums[idx-k]))
                bucket_dict.pop(old_bucket)
            
            bucket_dict[bucket] = num_tran

        return False

 

Idea (https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation)

We want to check if a number differs at most t with any of previous k elements by checking if any two numbers fall into the same bucket we shall create.

To do so, we first need to add every number by `sys.maxint`. This is to make sure every number can be transformed into an non-negative number so that we don’t need to worry about how to make different bucketing rules for negative and positive numbers.

For one transformed number, `num_tran`, we assign it to bucket `num_tran/(t+1)`. If two numbers fall into the same bucket, they must be of at most t difference. However, two numbers can also differ at most t if they are from two adjacent buckets. That’s why we have three condition checkings at line 25-27.

bucket_dict always has at most K elements. We maintain that by always popping out idx-k element. (line 30-32)

The time complexity is O(N) and the space complexity is O(K). 

 

Idea II

You can also maintain a balanced binary search tree of size K. Then you can always get the closest value of nums[i] (current visiting number) in the binary search tree in O(logK). If the closest value is within t of nums[i]’s range, you can return True.  Since you need to traverse all numbers in nums, and for each number you need to search in O(logK) time, the time complexity is O(NlogK) and the space complexity is O(K).

Reference:

https://leetcode.com/discuss/38177/java-o-n-lg-k-solution