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 <= 1051 <= nums[i] <= 1090 <= x < nums.lengthTo solve #2817 Minimum Absolute Difference Between Elements With Constraint, we must find two elements whose index difference is at least x while minimizing the absolute difference of their values. A brute‑force approach would compare every valid pair, but that leads to O(n^2) time, which is inefficient for large inputs.
A more optimal strategy uses an ordered set (balanced BST). As we iterate through the array, we maintain a sorted structure containing elements whose indices satisfy the constraint (at least x positions behind the current index). For each new value, we use lower_bound (or binary search in the ordered set) to find the closest values around it. Checking the nearest greater and smaller elements gives the minimum possible difference for that step.
This method efficiently narrows comparisons to only the most relevant candidates. Because insertion and search operations in an ordered set take O(log n), the overall algorithm runs in O(n log n) time with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Ordered Set with Binary Search | O(n log n) | O(n) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
<div class="_1l1MA">Let's only consider the cases where <code>i < j</code>, as the problem is symmetric.</div>
<div class="_1l1MA">For an index <code>j</code>, we are interested in an index <code>i</code> in the range <code>[0, j - x]</code> that minimizes <code>abs(nums[i] - nums[j])</code>.</div>
<div class="_1l1MA">For every index <code>j</code>, while going from left to right, add <code>nums[j - x]</code> to a set (C++ set, Java TreeSet, and Python sorted set).</div>
<div class="_1l1MA">After inserting <code>nums[j - x]</code>, we can calculate the closest value to <code>nums[j]</code> in the set using binary search and store the absolute difference. In C++, we can achieve this by using lower_bound and/or upper_bound.</div>
<div class="_1l1MA">Calculate the minimum absolute difference among all indices.</div>
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A brute-force approach checks every pair of elements whose indices satisfy the constraint, resulting in O(n^2) comparisons. For large arrays, this becomes too slow and exceeds typical coding interview time limits.
Problems involving ordered sets, binary search, and sliding constraints are common in FAANG-style interviews. This question tests your ability to combine data structures with index constraints to optimize pair comparisons.
An ordered set or balanced BST is the best choice because it keeps elements sorted while allowing fast insertion and lower_bound queries. This makes it easy to find the closest value to the current element and compute the minimum difference efficiently.
The optimal approach uses an ordered set (such as a balanced binary search tree). As you iterate through the array, maintain a sorted structure of elements that satisfy the index gap constraint and use binary search to find the closest values. This reduces the time complexity to O(n log n).