# Minimum Absolute Difference Between Elements With Constraint
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-absolute-difference-between-elements-with-constraint)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-difference-between-elements-with-constraint
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Ordered Set
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Capital One](https://scaleengineer.com/companies/capital-one), [Databricks](https://scaleengineer.com/companies/databricks)
---
## Problem
You are given a **0-indexed** integer array `nums` and an integer `x`.

Find the **minimum absolute difference** between two elements in the array that are at least `x` indices apart.

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

Return _an integer denoting the **minimum** absolute difference between two elements that are at least_ `x` _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:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `0 <= x < nums.length`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. We check every possible pair of indices `(i, j)` that satisfies the condition `abs(i - j) >= x`. For each valid pair, we calculate the absolute difference of the corresponding elements and keep track of the minimum difference found.
**Time:** O(n^2), where `n` is the number of elements in `nums`. The nested loops lead to a quadratic number of comparisons in the worst case (when `x` is small). · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
### Explanation
The core idea is to check every pair of indices `(i, j)` that satisfies the distance constraint `abs(i - j) >= x` and find the minimum difference `abs(nums[i] - nums[j])`.

*   Initialize a variable `minDifference` to a very large value, like `Integer.MAX_VALUE`.
*   Use two nested loops. The outer loop iterates `i` from `0` to `n-1`.
*   The inner loop iterates `j` from `i + x` to `n-1`. This setup ensures that for any pair `(i, j)`, the condition `j - i >= x` holds, which implies `abs(j - i) >= x`.
*   Inside the inner loop, calculate the absolute difference between `nums.get(i)` and `nums.get(j)`.
*   Compare this difference with `minDifference` and update `minDifference` if the new difference is smaller.
*   After the loops complete, `minDifference` will contain the result.

Here is the Java implementation:
```java
import java.util.List;

class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int minDifference = Integer.MAX_VALUE;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + x; j < n; j++) {
                int diff = Math.abs(nums.get(i) - nums.get(j));
                minDifference = Math.min(minDifference, diff);
            }
        }
        return minDifference;
    }
}
```
### Algorithm
*   Initialize a variable `minDifference` to `Integer.MAX_VALUE`.
*   Get the length of the array, `n`.
*   Loop for `i` from `0` to `n - 1`.
*   Inside this loop, start another loop for `j` from `i + x` to `n - 1`.
*   This ensures that for any pair of indices `(i, j)`, the condition `j - i >= x` is always met.
*   Calculate `currentDifference = abs(nums[i] - nums[j])`.
*   Update `minDifference = min(minDifference, currentDifference)`.
*   After both loops complete, return `minDifference`.

## Sliding Window with TreeSet
A more efficient approach involves iterating through the array while maintaining a sorted collection of elements that are eligible for comparison. For each element `nums[i]`, we need to find the closest value among elements `nums[j]` where `j <= i - x`. This can be done efficiently by using a balanced binary search tree (like Java's `TreeSet`) to store the elements from the "past" window `nums[0...i-x]`.
**Time:** O(n log n), where `n` is the number of elements in `nums`. The main loop runs `n - x` times. Inside the loop, `add`, `floor`, and `ceiling` operations on the `TreeSet` take O(log k) time, where `k` is the size of the set. The size `k` grows up to `n - x`. Therefore, the total time complexity is dominated by these operations, resulting in O((n-x) * log(n-x)), which simplifies to O(n log n). · **Space:** O(n). In the worst case (when `x` is small), the `TreeSet` can store up to `n - x` elements, leading to a space complexity of O(n).
**Pros:** Significantly more efficient than the brute-force approach.; Handles large inputs within typical time limits.; Relatively straightforward to implement using standard library data structures.
**Cons:** Requires more memory than the brute-force approach due to the `TreeSet`.
### Explanation
This optimized approach avoids redundant comparisons by using a data structure that keeps track of potential candidate elements in a sorted manner. We can iterate through the array and for each element `nums[i]`, efficiently find the closest value among the elements that are at least `x` indices before it. A balanced binary search tree, implemented as `TreeSet` in Java, is perfect for this task.

The algorithm proceeds as follows:
*   We iterate with an index `i` from `x` to `n-1`. For each `nums[i]`, we need to find a matching `nums[j]` where `j <= i - x`.
*   We maintain a `TreeSet` that stores the elements from the "past" window, i.e., `{nums[0], nums[1], ..., nums[i-x]}`.
*   In each iteration `i`, we first add `nums.get(i-x)` to the `TreeSet`. This makes it available for comparison with `nums.get(i)` and all subsequent elements.
*   Then, for the current element `nums.get(i)`, we search in the `TreeSet` for the two values that are closest to it:
    1.  The largest element in the set that is less than or equal to `nums.get(i)`. This is found using the `floor()` method.
    2.  The smallest element in the set that is greater than or equal to `nums.get(i)`. This is found using the `ceiling()` method.
*   We calculate the absolute difference between `nums.get(i)` and both the `floor` and `ceiling` (if they exist) and update our overall `minDifference`.

This way, for each element, we only perform a logarithmic time search instead of a linear scan.

Here is the Java implementation:
```java
import java.util.List;
import java.util.TreeSet;

class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        if (x == 0) {
            return 0;
        }
        int minDifference = Integer.MAX_VALUE;
        int n = nums.size();
        TreeSet<Integer> bst = new TreeSet<>();
        
        for (int i = x; i < n; i++) {
            bst.add(nums.get(i - x));
            
            Integer currentNum = nums.get(i);
            
            // Find the greatest element <= currentNum
            Integer floor = bst.floor(currentNum);
            if (floor != null) {
                minDifference = Math.min(minDifference, currentNum - floor);
            }
            
            // Find the smallest element >= currentNum
            Integer ceiling = bst.ceiling(currentNum);
            if (ceiling != null) {
                minDifference = Math.min(minDifference, ceiling - currentNum);
            }
        }
        return minDifference;
    }
}
```
### Algorithm
*   If `x` is 0, the answer is 0, so we can return immediately.
*   Initialize `minDifference` to `Integer.MAX_VALUE`.
*   Create a `TreeSet<Integer>` named `bst` to store elements from the valid 'past' window.
*   Loop for `i` from `x` to `n - 1`.
*   In each iteration, add the element `nums[i - x]` to the `bst`. This element is now part of the set of candidates for comparison.
*   For the current element `nums[i]`, find its closest neighbors in the `bst`:
    *   Find the `floor` of `nums[i]`: the largest element in `bst` that is less than or equal to `nums[i]`.
    *   Find the `ceiling` of `nums[i]`: the smallest element in `bst` that is greater than or equal to `nums[i]`.
*   If a `floor` element exists, calculate `diff = nums[i] - floor` and update `minDifference`.
*   If a `ceiling` element exists, calculate `diff = ceiling - nums[i]` and update `minDifference`.
*   After the loop, return `minDifference`.

# Solutions
### Java

```java
class Solution {
public
  int minAbsoluteDifference(List<Integer> nums, int x) {
    TreeMap<Integer, Integer> tm = new TreeMap<>();
    int ans = 1 << 30;
    for (int i = x; i < nums.size(); ++i) {
      tm.merge(nums.get(i - x), 1, Integer : : sum);
      Integer key = tm.ceilingKey(nums.get(i));
      if (key != null) {
        ans = Math.min(ans, key - nums.get(i));
      }
      key = tm.floorKey(nums.get(i));
      if (key != null) {
        ans = Math.min(ans, nums.get(i) - key);
      }
    }
    return ans;
  }
}

```

### Python

```python
from sortedcontainers import SortedList class Solution : def minAbsoluteDifference ( self , nums : List [ int ], x : int ) -> int : sl = SortedList () ans = inf for i in range ( x , len ( nums )): sl . add ( nums [ i - x ]) j = bisect_left ( sl , nums [ i ]) if j < len ( sl ): ans = min ( ans , sl [ j ] - nums [ i ]) if j : ans = min ( ans , nums [ i ] - sl [ j - 1 ]) return ans
```

### CPP

```cpp
class Solution {
public:
  int minAbsoluteDifference(vector<int> &nums, int x) {
    int ans = 1 << 30;
    multiset<int> s;
    for (int i = x; i < nums.size(); ++i) {
      s.insert(nums[i - x]);
      auto it = s.lower_bound(nums[i]);
      if (it != s.end()) {
        ans = min(ans, *it - nums[i]);
      }
      if (it != s.begin()) {
        --it;
        ans = min(ans, nums[i] - *it);
      }
    }
    return ans;
  }
};

```