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
Python's priority queue heapq is implemented via list, not like C++ or JAVA via Balanced BST. So heapq can not search range, like searching for the smallest node larger than target value (BST successor).
Below is a way to implement a not balanced BST to support that kind of requirement. [Not accepted yet]
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
if k <=0 or t < 0 or not nums:
return False
priorityQ = PriorityQ([])
for i in range(len(nums)):
candidate = priorityQ.successor(nums[i] - t)
return nums[i] - t, candidate
if candidate and candidate.val <= nums[i] + t:
return True
# if i >= k - 1: # This is not k distance, this is k - 1 distance
# priorityQ.delete(nums[i - k + 1])
if i >= k:
priorityQ.delete(nums[i - k])
priorityQ.insert(nums[i])
return False
class TreeNode(object):
def __init__(self, val):
self.left = None
self.right = None
self.val = val
class PriorityQ(object):
def __init__(self, nums):
if not nums:
self.root = None
else:
self.root = TreeNode(nums[0])
if len(nums) > 1:
for i in range(1, len(nums)):
self.insert(nums[i])
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert(self.root, val)
def successor(self, val):
if not self.root:
return None
return self._successor(self.root, val, None)
def delete(self, val):
self._delete(self.root, val)
def _insert(self, root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = self._insert(root.left, val)
else:
root.right = self._insert(root.right, val)
return root
def _successor(self, root, val, successor):
if not root:
return successor
if val < root.val:
return self._successor(root.left, val, root)
else:
return self._successor(root.right, val, successor)
def _delete(self, root, val):
if not root:
return None
if val < root.val:
root.left = self._delete(root.left, val)
return root
elif val > root.val:
root.right = self._delete(root.right, val)
return root
else:
if not root.left and not root.right:
return None
elif not root.left:
return root.right
elif not root.right:
return root.left
else:
successorInRightChild = self._successor(root, root.val, None)
root.val = successorInRightChild.val
root.right = self._delete(root.right, successorInRightChild.val)
return root
