<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 SortedList
class Solution:
    # note the symmetry. If A[1], A[3] is the best pair
    # then we couldve chosen it when i=1 and j=3 or when i=3 and j=1.
    # hence we can just fix i < j.
    # Now for every A[i] we can find the best A[j] that can be paired
    # with it.
    def minAbsoluteDifference(self, A: List[int], x: int) -> int:
        if x == 0: return 0
        sl = SortedList(A[x:])
        res = inf
        for i in range(len(A) - x):
            j = sl.bisect_left(A[i])
            if j < len(sl):
                res = min(res, abs(A[i] - sl[j]))
            if j - 1 >= 0:
                res = min(res, abs(A[i] - sl[j-1]))
            sl.remove(A[i + x])
        return res
    
    # An alternate observation is the min diff in an array is
    # the min of the pairwise diff of the sorted array.
    # Hence we can sort the array by values and track the
    # values that can be on the left or right of A[i].
    # Then every time we pop from the heap it must be the most optimal
    # choice since they are sorted by values.
    def minAbsoluteDifference(self, A: List[int], x: int) -> int:
        res = inf
        min_pq = []
        max_pq = []
        for val, i in sorted(zip(A, count())):
            # NOTE: gotta put this in front for x = 0 case
            heappush(min_pq, (+i, val))
            heappush(max_pq, (-i, val))
            # left side
            while min_pq and min_pq[0][0] <= i - x:
                res = min(res, abs(heappop(min_pq)[1] - val))
            # right side
            while max_pq and i + x <= -max_pq[0][0]:
                res = min(res, abs(heappop(max_pq)[1] - val))
        return res
    
    def minAbsoluteDifference(self, A: List[int], x: int) -> int:
        s = [-inf] + sorted(A[x:]) + [inf]
        nxt = list(range(len(s)))
        prv = list(range(len(s)))
        idx = { s[i]: i for i in range(len(s) - 1, -1, -1) }

        def find(par, i):
            if i == par[i]: return i
            par[i] = find(par, par[i])
            return par[i]

        #print(s)
        
        res = inf
        for i in range(len(A) - x):
            j = bisect_left(s, A[i])

            j = find(nxt, j)
            assert j == nxt[j]
            if j < len(s) - 1:
                res = min(res, abs(A[i] - s[j]))
            
            j = find(prv, j - 1)
            assert j == prv[j]
            if j > 0:
                res = min(res, abs(A[i] - s[j]))
            
            # print(nxt)
            # print(prv)
            # print()
            assert nxt[ idx[A[i+x]] ] == idx[A[i+x]]
            assert prv[ idx[A[i+x]] ] == idx[A[i+x]]
            nxt[ idx[A[i+x]] ] += 1
            prv[ idx[A[i+x]] ] -= 1
            if s[idx[A[i+x]] + 1] == A[i+x]:
                idx[A[i+x]] += 1
        
        # print(nxt)
        # print(prv)
        # print()

        assert find(nxt, 1) == len(s) - 1
        assert find(prv, len(s) - 2) == 0
        return res
        
#         i = bisect_left(s, for thing)
#         i = find(i)
#         find(i-1)
#         res = min..
#         delete, nxt[ idx[i+x] ] += 1
        

# # also neat solution with DSU/union find, but dont quite get it


# sorted list A[:x], rm elems in here
# path compression on idx?
# map val -> orig idx
# dupes??
# delete: nxt[i] = i + 1, or nxt[i] += 1 since assert nxt[i] == i
743