# LC 2817. Minimum Absolute Difference Between Elements With Constraint

### [Problem link](https://leetcode.com/problems/minimum-absolute-difference-between-elements-with-constraint/)

###### tags: `leedcode` `python` `medium` `SortedList` `Binary Search`

You are given a **0-indexed** integer array <code>nums</code> and an integer <code>x</code>.

Find the **minimum absolute difference** between two elements in the array that are at least <code>x</code> indices apart.

In other words, find two indices <code>i</code> and <code>j</code> such that <code>abs(i - j) >= x</code> and <code>abs(nums[i] - nums[j])</code> is minimized.

Return an integer denoting the **minimum** absolute difference between two elements that are at least <code>x</code> indices apart.

**Example 1:**

Input: nums = [4,3,2,4], x = 2
Output: 0
Explanation: 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.

**Example 2:**

Input: nums = [5,3,2,10,15], x = 1
Output: 1
Explanation: 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.

**Example 3:**

Input: nums = [1,2,3,4], x = 3
Output: 3
Explanation: 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.

**Constraints:**

- <code>1 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] <= 10⁹</code>
- <code>0 <= x < nums.length</code>

## Solution 1 - Binary Search

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)
        st = SortedList([float('-inf'), float('inf')])
        res = float('inf')

        left = 0
        for right in range(x, n):
            st.add(nums[left])
            idx = st.bisect_left(nums[right])
            res = min(res, abs(st[idx] - nums[right]), abs(st[idx - 1] - nums[right]))
            left += 1

        return res

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(n) |

## Note
第一次用SortedList, 感覺蠻好用的, 新增 刪除 查詢, 幾乎各種操作都是O(logn), 可以學起來.