Contains Duplicate III

contains_duplicate_iii.py

"""
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the
absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
"""
from typing import List


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        """
        Brute force. Time complexity: O(n * k)
        40 / 41 test cases passed
        """
        if not nums:
            return False
        for i in range(len(nums)):
            for j in range(i + 1, i + k + 1):
                if j >= len(nums):
                    break
                if abs(nums[i] - nums[j]) <= t:
                    return True
        return False

    def contains_nearby_almost_duplicate_efficient(
        self, nums: List[int], k: int, t: int
    ) -> bool:
        """
        Bucket sort algo. Time complexity: O(n)
        """
        if not nums:
            return False
        elif t < 0:
            return False
        cache = {}
        for i in range(len(nums)):
            if i - k > 0:
                bucket_id = nums[i - k - 1] // (t + 1)
                del cache[bucket_id]
            bucket_id = nums[i] // (t + 1)
            cond_1 = bucket_id in cache
            cond_2 = bucket_id - 1 in cache and abs(cache[bucket_id - 1] - nums[i]) <= t
            cond_3 = bucket_id + 1 in cache and abs(cache[bucket_id + 1] - nums[i]) <= t
            if cond_1 or cond_2 or cond_3:
                return True
            cache[bucket_id] = nums[i]
        return False