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 theminimum absolute difference between two elements that are at least x indices apart.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= x < nums.length

Solution

Method 1 – Ordered Set (Balanced BST)

Intuition

To find the minimum absolute difference between elements at least x indices apart, we can use an ordered set to keep track of elements that are at least x indices behind the current index. For each index, we check the closest values in the set to minimize the absolute difference.

Approach

  1. Iterate through the array, and for each index i ≥ x, insert nums[i-x] into an ordered set.
  2. For each index i ≥ x, use the set to find the closest value to nums[i] (both lower and upper bounds).
  3. Update the minimum absolute difference accordingly.
  4. Return the minimum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums, int x) {
        set<int> st;
        int ans = INT_MAX;
        for (int i = x; i < nums.size(); ++i) {
            st.insert(nums[i-x]);
            auto it = st.lower_bound(nums[i]);
            if (it != st.end()) ans = min(ans, abs(*it - nums[i]));
            if (it != st.begin()) {
                --it;
                ans = min(ans, abs(*it - nums[i]));
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func minAbsoluteDifference(nums []int, x int) int {
    import "sort"
    st := []int{}
    ans := 1 << 30
    for i := x; i < len(nums); i++ {
        st = append(st, nums[i-x])
        sort.Ints(st)
        idx := sort.SearchInts(st, nums[i])
        if idx < len(st) {
            if abs(st[idx]-nums[i]) < ans {
                ans = abs(st[idx]-nums[i])
            }
        }
        if idx > 0 {
            if abs(st[idx-1]-nums[i]) < ans {
                ans = abs(st[idx-1]-nums[i])
            }
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minAbsoluteDifference(int[] nums, int x) {
        TreeSet<Integer> st = new TreeSet<>();
        int ans = Integer.MAX_VALUE;
        for (int i = x; i < nums.length; ++i) {
            st.add(nums[i-x]);
            Integer hi = st.ceiling(nums[i]);
            Integer lo = st.floor(nums[i]);
            if (hi != null) ans = Math.min(ans, Math.abs(hi - nums[i]));
            if (lo != null) ans = Math.min(ans, Math.abs(lo - nums[i]));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minAbsoluteDifference(nums: IntArray, x: Int): Int {
        val st = sortedSetOf<Int>()
        var ans = Int.MAX_VALUE
        for (i in x until nums.size) {
            st.add(nums[i-x])
            val hi = st.ceiling(nums[i])
            val lo = st.floor(nums[i])
            if (hi != null) ans = minOf(ans, abs(hi - nums[i]))
            if (lo != null) ans = minOf(ans, abs(lo - nums[i]))
        }
        return ans
    }
    fun abs(a: Int) = if (a < 0) -a else a
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def min_absolute_difference(nums: list[int], x: int) -> int:
    import bisect
    st: list[int] = []
    ans = float('inf')
    for i in range(x, len(nums)):
        bisect.insort(st, nums[i-x])
        idx = bisect.bisect_left(st, nums[i])
        if idx < len(st):
            ans = min(ans, abs(st[idx] - nums[i]))
        if idx > 0:
            ans = min(ans, abs(st[idx-1] - nums[i]))
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn min_absolute_difference(nums: Vec<i32>, x: i32) -> i32 {
        use std::collections::BTreeSet;
        let mut st = BTreeSet::new();
        let mut ans = i32::MAX;
        for i in x as usize..nums.len() {
            st.insert(nums[i-x as usize]);
            if let Some(&hi) = st.range(nums[i]..).next() {
                ans = ans.min((hi - nums[i]).abs());
            }
            if let Some(&lo) = st.range(..=nums[i]).next_back() {
                ans = ans.min((lo - nums[i]).abs());
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    minAbsoluteDifference(nums: number[], x: number): number {
        const st: number[] = [];
        let ans = Number.MAX_SAFE_INTEGER;
        for (let i = x; i < nums.length; ++i) {
            st.push(nums[i-x]);
            st.sort((a, b) => a - b);
            const idx = st.findIndex(v => v >= nums[i]);
            if (idx !== -1) ans = Math.min(ans, Math.abs(st[idx] - nums[i]));
            if (idx > 0) ans = Math.min(ans, Math.abs(st[idx-1] - nums[i]));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
    • Each insertion and search in the ordered set is O(log n).
  • 🧺 Space complexity: O(n)
    • For the ordered set.