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

# 13:26 started

# for a given index i, you have [0, i-x] and [i + x, n - 1] ranges

# i = 3, x = 2, n = 6

# [0, 1] and [5, 5]

# 0 1 2 3 4 5
# - -   ^   -


# two nested loops:
# time: O(n**2)
# memory: O(1)
# 13:30. can we do better?

# find_closest(value, i, k)

# maintain two sorted containers - for range before the value and range after the value.

# add and pop elements from it.
# find elements the is closests to given.

# balanced tree. add/pop = O(logn); find - O(logn)
# sortedcontainers. add/pop = O(sqrtn) but with good constant factor; find = O(logn)

# with sortedcontainers:
# time: O(n**(3/2))
# memory: O(n)
# so we traded some memory for better time complexity

# 13:38 - implemented first approach, time limit exceeded; 2008/2013 passed

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        if len(nums) < 10:
            return self.minAbsoluteDifferenceQ(nums, x)
        n = len(nums)
        best_result = 10**10
        before = SortedList()
        # XXX not working for x == 0?
        after = SortedList(nums[x - 1:])
        for i, val in enumerate(nums):
            last1 = i - x
            if last1 >= 0:
                before.add(nums[last1])
            removed2 = i + x - 1
            if removed2 >= 0 and removed2 < n:
                after.discard(nums[removed2])
            if before:
                found = before.bisect_left(val)
                if found >= len(before):
                    found_val = before[len(before) - 1]
                else:
                    found_val = before[found]
                r = abs(found_val - val)
                if r < best_result:
                    best_result = r

            if after:
                found = after.bisect_left(val)
                if found >= len(after):
                    found_val = after[-1]
                else:
                    found_val = after[found]
                r = abs(found_val - val)
                if r < best_result:
                    best_result = r

        return best_result

    def minAbsoluteDifferenceQ(self, nums: List[int], x: int) -> int:
        n = len(nums)
        best_result = 10**10
        for i, val in enumerate(nums):
            end1 = i - x + 1
            start1 = 0
            start2 = i + x
            end2 = n
            if end1 > start1:
                for j in range(start1, end1):
                    r = abs(nums[j] - val)
                    if r < best_result:
                        best_result = r
            if end2 > start2:
                for j in range(start2, end2):
                    r = abs(nums[j] - val)
                    if r < best_result:
                        best_result = r
        return best_result  
        
1406