LC-0220 Hard LeetCode

220. Contains Duplicate III

Array Sliding Window Sorting Bucket Sort Ordered Set

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 24% Topics: Array, Sliding Window, Sorting, Bucket Sort, Ordered Set

Reading material

Arrays & Hashing 12 min Sliding Window 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n * t)
# Space: O(max(k, t))

import collections


class Solution(object):
    # @param {integer[]} nums
    # @param {integer} k
    # @param {integer} t
    # @return {boolean}
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if k < 0 or t < 0:
            return False
        window = collections.OrderedDict()
        for n in nums:
            # Make sure window size
            if len(window) > k:
                window.popitem(False)

            bucket = n if not t else n // t
            # At most 2t items.
            for m in (window.get(bucket - 1), window.get(bucket), window.get(bucket + 1)):
                if m is not None and abs(n - m) <= t:
                    return True
            window[bucket] = n
        return False

Solution from kamyu104/LeetCode-Solutions · MIT