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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Starter code: class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        

Solutions:
class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if len(nums) < 2 or k <= 0 or t < 0:
			return False
		if t == 0:
			visited = set()
			for (i, n) in enumerate(nums):
				if n in visited:
					return True
				visited.add(n)
				if i >= k:
					visited.remove(nums[i - k])
			return False
		bucket = {}
		for (i, n) in enumerate(nums):
			b = n // t
			if b in bucket:
				return True
			if b + 1 in bucket and abs(bucket[b + 1] - n) <= t:
				return True
			if b - 1 in bucket and abs(bucket[b - 1] - n) <= t:
				return True
			bucket[b] = n
			if i >= k:
				del bucket[nums[i - k] // t]
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		nums2 = [(n, i) for (i, n) in enumerate(nums)]
		nums2 = sorted(nums2)
		print(nums2)
		for i in range(1, len(nums2)):
			j = i - 1
			(a, n) = nums2[j]
			(b, m) = nums2[i]
			while abs(a - b) <= t:
				if abs(n - m) <= k:
					return True
				j -= 1
				if j < 0:
					break
				(a, n) = nums2[j]
		return False


class Solution(object):

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if k < 1 or t < 0:
			return False
		import sys
		bh = {}
		w = t + 1
		for i in range(len(nums)):
			n_i = nums[i]
			n_i_w = n_i // w
			if n_i_w in bh:
				return True
			if n_i_w - 1 in bh and abs(n_i - bh[n_i_w - 1]) < w:
				return True
			if n_i_w + 1 in bh and abs(n_i - bh[n_i_w + 1]) < w:
				return True
			bh[n_i_w] = nums[i]
			if len(bh) > k:
				del bh[nums[i - k] // w]
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if t < 0:
			return False
		w = t + 1
		d = {}
		for i in range(0, len(nums)):
			m = nums[i] // w
			if m in d:
				return True
			if m - 1 in d and abs(nums[i] - d[m - 1]) <= t:
				return True
			if m + 1 in d and abs(nums[i] - d[m + 1]) <= t:
				return True
			d[m] = nums[i]
			if i >= k:
				del d[nums[i - k] // w]
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if t < 0:
			return False
		n = len(nums)
		buckets = {}
		w = t + 1
		for i in range(n):
			bucket_num = nums[i] // w
			if bucket_num in buckets:
				return True
			if bucket_num - 1 in buckets and abs(nums[i] - buckets[bucket_num - 1]) < w:
				return True
			if bucket_num + 1 in buckets and abs(nums[i] - buckets[bucket_num + 1]) < w:
				return True
			buckets[bucket_num] = nums[i]
			if i >= k:
				del buckets[nums[i - k] // w]
		return False


class Solution:

	def equalSol(self, nums, k):
		if k == 0:
			return False
		d = {}
		for i in range(len(nums)):
			if nums[i] in d.keys() and abs(i - d[nums[i]]) <= k:
				return True
			else:
				d[nums[i]] = i
		return False

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if k == 0:
			return False
		if t == 0:
			return self.equalSol(nums, k)
		for i in range(len(nums)):
			for j in range(1, k + 1):
				if i + j < len(nums) and abs(nums[i] - nums[i + j]) <= t:
					return True
				if i - j >= 0 and abs(nums[i] - nums[i - j]) <= t:
					return True
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		buckets = {}
		for (i, v) in enumerate(nums):
			(bucket_num, offset) = (v // t, 1) if t else (v, 0)
			for idx in range(bucket_num - offset, bucket_num + offset + 1):
				if idx in buckets and abs(buckets[idx] - nums[i]) <= t:
					return True
			buckets[bucket_num] = nums[i]
			if len(buckets) > k:
				del buckets[nums[i - k] // t if t else nums[i - k]]
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if len(nums) == 0 or len(nums) == 1 or k < 1 or (t < 0):
			return False
		d = collections.OrderedDict()
		for i in nums:
			key = i if not t else i // t
			for j in (d.get(key - 1), d.get(key), d.get(key + 1)):
				if j != None and abs(j - i) <= t:
					return True
			if len(d) == k:
				d.popitem(False)
			d[key] = i
		return False


class Solution:

	def containsNearbyAlmostDuplicate(self, nums, k, t):
		if k < 1 or t < 0:
			return False
		m = len(nums)
		if m == 0:
			return False
		buckets = {}
		_min = 0
		for i in range(m):
			num = nums[i] - _min
			bucket = num // (t + 1)
			flag = bucket in buckets or (bucket - 1 in buckets and abs(buckets[bucket - 1] - num) <= t) or (bucket + 1 in buckets and abs(buckets[bucket + 1] - num) <= t)
			if flag:
				return True
			if len(buckets) >= k:
				del buckets[(nums[i - k] - _min) // (t + 1)]
			buckets[bucket] = num
		return False