<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> and an integer <code>x</code>.</p>

<p>Find the <strong>minimum absolute difference</strong> between two elements in the array that are at least <code>x</code> indices apart.</p>

<p>In other words, find two indices <code>i</code> and <code>j</code> such that <code>abs(i - j) &gt;= x</code> and <code>abs(nums[i] - nums[j])</code> is minimized.</p>

<p>Return<em> an integer denoting the <strong>minimum</strong> absolute difference between two elements that are at least</em> <code>x</code> <em>indices apart</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [4,3,2,4], x = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can select nums[0] = 4 and nums[3] = 4. 
They are at least 2 indices apart, and their absolute difference is the minimum, 0. 
It can be shown that 0 is the optimal answer.
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,3,2,10,15], x = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can select nums[1] = 3 and nums[2] = 2.
They are at least 1 index apart, and their absolute difference is the minimum, 1.
It can be shown that 1 is the optimal answer.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4], x = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can select nums[0] = 1 and nums[3] = 4.
They are at least 3 indices apart, and their absolute difference is the minimum, 3.
It can be shown that 3 is the optimal answer.
</pre>

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

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

class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
        self.height = 1

class AVLTree:
    def __init__(self):
        self.root = None
    
    def add_value(self, value):
        self.root = self.add(self.root, value)

    def add(self, root, value):
        if not root:
            return TreeNode(value)
        if root.val == value:
            return root
        if value < root.val:
            root.left = self.add(root.left, value)
        else:
            root.right = self.add(root.right, value)
        root.height = 1 + max(self.height(root.left), self.height(root.right))
        bal = self.balance(root)
        if bal > 1:
            if value > root.left.val:
                root.left = self.left_rotate(root.left)
            root = self.right_rotate(root)
        elif bal < -1:
            if value < root.right.val:
                root.right = self.right_rotate(root.right)
            root = self.left_rotate(root)
        return root

    def height(self, root):
        return root.height if root else 0

    def balance(self, root):
        return self.height(root.left) - self.height(root.right) if root else 0

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self.height(z.left), self.height(z.right))
        y.height = 1 + max(self.height(y.left), self.height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self.height(z.left), self.height(z.right))
        y.height = 1 + max(self.height(y.left), self.height(y.right))

        return y
    
    def find(self, value):
        res = inf
        cur = self.root
        while cur:
            res = min(res, abs(cur.val - value))
            if value < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        return res

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        l = 0
        res = inf
        tree = AVLTree()
        for r in range(len(nums)):
            if r - l == x:
                tree.add_value(nums[l])
                l += 1
            res = min(res, tree.find(nums[r]))
        return res

1672