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

import heapq

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        
        # minimum abs difference between two elements that are at least x indices apart
        # return: integer denoting the minimum absolute difference between 2 elements
        # min_heap stores "smallest" indices on left side
        # max_heap stores "largest" indices on right side
        # 1, 2, 4, 4

        res = float('inf')
        min_heap, max_heap = [], []
        nums = sorted([(idx, nums[idx]) for idx in range(len(nums))], key=lambda x: x[1])
        res = float('inf')

        for i in range(len(nums)):
            cur_indice, cur_val = nums[i]

            heapq.heappush(min_heap, nums[i])
            heapq.heappush(max_heap, (cur_indice * -1, cur_val))

            while (len(min_heap) > 0 and cur_indice - min_heap[0][0] >= x):
                res = min(res, abs(min_heap[0][1] - cur_val))
                heapq.heappop(min_heap)
            
            while (len(max_heap) > 0 and max_heap[0][0] * (-1) - cur_indice >= x):
                res = min(res, abs(max_heap[0][1] - cur_val))
                heapq.heappop(max_heap)
            

        
        return res
            


                
                


        
        return res





        
43600