Watch 10 video solutions for Minimum Absolute Difference Between Elements With Constraint, a medium level problem involving Array, Binary Search, Ordered Set. This walkthrough by Prakhar Agrawal has 2,651 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthProblem Overview: You are given an integer array nums and an integer x. The goal is to find the minimum absolute difference between two elements nums[i] and nums[j] such that |i - j| ≥ x. The constraint prevents comparing nearby elements, so the algorithm must track only values that are far enough apart in the array.
Approach 1: Brute Force with Constraint Check (O(n²) time, O(1) space)
The straightforward approach checks every valid pair. Iterate through the array using two nested loops and only evaluate pairs where |i - j| ≥ x. For each valid pair, compute abs(nums[i] - nums[j]) and track the minimum. This method is simple and clearly demonstrates the constraint logic, but it performs up to n² comparisons and becomes impractical for large inputs.
Approach 2: Sliding Window with Sorted List (O(n log n) time, O(n) space)
The optimized approach maintains a dynamically sorted structure of eligible elements. As you iterate through the array, add the element nums[i - x] into an ordered structure once it becomes valid for comparison. This ensures every stored value satisfies the index distance constraint.
Use an ordered set or sorted list and locate the closest values to nums[i] using binary search. Specifically, find the first element greater than or equal to nums[i] and also check the previous element. These two candidates produce the smallest possible absolute difference in a sorted structure. Update the global minimum after each comparison.
The key insight: in a sorted structure, the nearest values to a number must lie directly adjacent in order. Binary search finds those candidates in O(log n), and insertion also costs O(log n) for balanced trees (or O(n) in Python lists but still efficient in practice). Iterating once through the array results in overall O(n log n) time.
Recommended for interviews: Start with the brute force idea to show you understand the constraint and pair comparison logic. Then move to the ordered-set solution. Interviewers typically expect the O(n log n) approach using a balanced tree, TreeSet, or sorted container because it demonstrates knowledge of binary search on dynamic data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Constraint Check | O(n²) | O(1) | Good for understanding the constraint logic or very small arrays |
| Sliding Window with Sorted List / Ordered Set | O(n log n) | O(n) | Best general solution; efficient for large inputs and typical interview expectations |