LeetCode 220 Contains Duplicate III

LeetCode 220 Contains Duplicate III Problem

Download Code
from collections import OrderedDict
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        # https://discuss.leetcode.com/topic/19991/o-n-python-using-buckets-with-explanation-10-lines
        # Bucket sort. Each bucket has size of t. For each number, the possible
        # candidate can only be in the same bucket or the two buckets besides.
        # Keep as many as k buckets to ensure that the difference is at most k.
        buckets = {}
        for i, v in enumerate(nums):
            # t == 0 is a special case where we only have to check the bucket
            # that v is in.
            bucketNum, offset = (v / t, 1) if t else (v, 0)
            for idx in xrange(bucketNum - offset, bucketNum + offset + 1):
                if idx in buckets and abs(buckets[idx] - nums[i]) <= t:
                    return True

            buckets[bucketNum] = nums[i]
            if len(buckets) > k:
                # Remove the bucket which is too far away. Beware of zero t.
                del buckets[nums[i - k] / t if t else nums[i - k]]

        return False
Download Contains Duplicate III.py

List of all Contains Duplicate III problems

Leetcode 220 Contains Duplicate III problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.