<p>You are given an integer array <code>nums</code> and two integers <code>indexDiff</code> and <code>valueDiff</code>.</p>

<p>Find a pair of indices <code>(i, j)</code> such that:</p>

<ul>
	<li><code>i != j</code>,</li>
	<li><code>abs(i - j) &lt;= indexDiff</code>.</li>
	<li><code>abs(nums[i] - nums[j]) &lt;= valueDiff</code>, and</li>
</ul>

<p>Return <code>true</code><em> if such pair exists or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
<strong>Output:</strong> true
<strong>Explanation:</strong> We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --&gt; 0 != 3
abs(i - j) &lt;= indexDiff --&gt; abs(0 - 3) &lt;= 3
abs(nums[i] - nums[j]) &lt;= valueDiff --&gt; abs(1 - 1) &lt;= 0
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
<strong>Output:</strong> false
<strong>Explanation:</strong> After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= indexDiff &lt;= nums.length</code></li>
	<li><code>0 &lt;= valueDiff &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        bst = None
        for i in range(len(nums)):
            if bst is None:
                bst = AVLTreeNode(nums[i])
            else:
                if abs(nums[i] - bst.findClosest(nums[i])) <= valueDiff:
                    return True
                bst = bst.insert(nums[i])
                if i - indexDiff >= 0:
                    bst = bst.remove(nums[i - indexDiff])
        return False

class AVLTreeNode:
    def __init__(self, value):
        self.value = value
        self.balance = 0  # defined as self.left.height - self.right.height
        self.height = 1
        self.left = None  # smaller than or equal to
        self.right = None

    def insert(self, k):
        if k <= self.value:
            if not self.left:
                self.left = AVLTreeNode(k)
            else:
                self.left = self.left.insert(k)
        else:
            if not self.right:
                self.right = AVLTreeNode(k)
            else:
                self.right = self.right.insert(k)
        self.height = 1 + max(self.left.height if self.left else 0, self.right.height if self.right else 0)
        self.balance = (self.left.height if self.left else 0) - (self.right.height if self.right else 0)

        # balance self
        if self.balance > 1:
            if self.left.balance >= 0:
                return self.right_rotate()
            else:
                self.left = self.left.left_rotate()
                return self.right_rotate()
        elif self.balance < -1:
            if self.right.balance <= 0:
                return self.left_rotate()
            else:
                self.right = self.right.right_rotate()
                return self.left_rotate()
        return self

    def remove(self, k):
        if k < self.value:
            if self.left:
                self.left = self.left.remove(k)
        elif k > self.value:
            if self.right:
                self.right = self.right.remove(k)
        else:
            if not self.left:
                return self.right
            elif not self.right:
                return self.left
            temp = self.right.find_min()
            self.value = temp.value
            self.right = self.right.remove(temp.value)

        self.height = 1 + max(self.left.height if self.left else 0, self.right.height if self.right else 0)
        self.balance = (self.left.height if self.left else 0) - (self.right.height if self.right else 0)

        if self.balance > 1:
            if self.left.balance >= 0:
                return self.right_rotate()
            else:
                self.left = self.left.left_rotate()
                return self.right_rotate()
        elif self.balance < -1:
            if self.right.balance <= 0:
                return self.left_rotate()
            else:
                print(self.right)
                self.right = self.right.right_rotate()
                return self.left_rotate()
        return self

    def find_min(self):
        if self.left is None:
            return self
        else:
            return self.left.find_min()

    def findClosest(self, k):
        closest = self.value
        if k < self.value:
            if self.left:
                left_closest = self.left.findClosest(k)
                if abs(k - left_closest) < abs(k - closest):
                    closest = left_closest
        elif k > self.value:
            if self.right:
                right_closest = self.right.findClosest(k)
                if abs(k - right_closest) < abs(k - closest):
                    closest = right_closest
        return closest

    def left_rotate(self):
        new_root = self.right
        if new_root is None:  # Ensure the new root exists
            return self
        self.right = new_root.left
        new_root.left = self
        self.height = 1 + max(self.left.height if self.left else 0, self.right.height if self.right else 0)
        new_root.height = 1 + max(new_root.left.height if new_root.left else 0, new_root.right.height if new_root.right else 0)
        return new_root

    def right_rotate(self):
        new_root = self.left
        if new_root is None:
            return self  # Safety check, should not happen if the tree is correctly balanced
        self.left = new_root.right
        new_root.right = self
        # Update heights
        self.height = 1 + max(self.left.height if self.left else 0, self.right.height if self.right else 0)
        new_root.height = 1 + max(new_root.left.height if new_root.left else 0, new_root.right.height if new_root.right else 0)
        return new_root


36251