<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>

from sortedcontainers import SortedSet

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:

        # we want to find the min abs difference between two values that are at least X indexes apart
        # at a given index i, there will be some set of numbers before, and after
        # to find the minimum value compared to this number, we want to binary search for it within the before and after
        # to binary search, we need them to be sorted
        # but since these before/after lists are dynamically changing in size, we need a data structure that does this for us
        # so we can use a sorted list to represent before and after
        # at a given index I, binary search for the number of nums[i] within both lists, compare to a global min
        # then add nums[i - x + 1] to the before sorted list, and remove nums[i+X] from the after list

        if x == 0:
            return 0
        
        before, after = SortedSet(), SortedSet()
        mapping = {'b': before, 'a': after}
        res = float('inf')

        for i in range(x, len(nums)):
            after.add(nums[i])
        
        for i in range(len(nums)):
            val = nums[i]
            values = []
            
            values.append([before.bisect(val), 'b'])
            values.append([after.bisect(val), 'a'])

            for v, ch in values:
                if mapping[ch]:
                    for neighbor in (-1, 0, 1):
                        if 0 <= v + neighbor < len(mapping[ch]):
                            res = min(res, abs(val - mapping[ch][v + neighbor]))
            
            if i >= x - 1:
                before.add(nums[i - x + 1])
            
            if i < len(nums) - x:
                after.discard(nums[i + x])

        return res


        

        


        
   
 
35500