Contain Duplicate III

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