<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 Solution:
    def minAbsoluteDifference1(self, nums: List[int], x: int) -> int:
        min_abs_diff = float('inf')
        for i in range(len(nums) - x):
            for j in range(i + x, len(nums)):
                min_abs_diff = min(min_abs_diff, abs(nums[i] - nums[j]))
        return min_abs_diff

    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        # If we're looking at any given index i, we have to:

        # First, check nums[i] against all nums[j] such that j <= i - x and j >= i + x.
        # Then, find the smallest abs(nums[j] - nums[i]).

        # A min heap will cover all j <= i - x and a max heap will cover all j >= i + x.

        # The minimum absolute difference will just be the minimum abs(nums[j] - nums[i]) across all i.
        
        sorted_nums = sorted((val, idx) for idx, val in enumerate(nums))
        left_heap = []
        right_heap = []

        min_diff = float('inf')

        for val, idx in sorted_nums:
            heapq.heappush(left_heap, (idx, val)) 
            heapq.heappush(right_heap, (-idx, val)) 
        
            # smallest index in the heap (i.e. the root) is more than x away from idx
            while len(left_heap) > 0 and left_heap[0][0] <= idx - x:
                # updates min_diff if the difference between val and the root's val is smaller
                min_diff = min(min_diff, val - heapq.heappop(left_heap)[1])             
                
            # largest index in the heap (i.e. the root) is more than x away from idx
            while len(right_heap) > 0 and right_heap[0][0] <= -(x + idx):
                min_diff = min(min_diff, val - heapq.heappop(right_heap)[1])   

        return min_diff

                
1273