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.
This solution uses the SortedList from the 'sortedcontainers' module for efficient insertion and access. As we iterate over elements in 'nums', we maintain a sliding window of the last 'x' elements in sorted order. For each element, we check adjacent elements from the sorted list to find the minimum difference and update our result.
Python
Java
JavaScript
C++
C#
Time Complexity: O(n log x), where n is the length of the array and x is the constraint for indices apart. Space Complexity: O(x) due to storing the elements in the sorted list.
This Python code loops through each permissible pair, checks if their index difference meets the constraint and calculates the absolute difference to find the minimum.
Python
Java
JavaScript
C++
C#
Time Complexity: O(n^2), as all pairs are checked. Space Complexity: O(1), as only simple variables are used.
We create an ordered set to store the elements whose distance to the current index is at least x.
Next, we enumerate from index i = x, each time we add nums[i - x] into the ordered set. Then we find the two elements in the ordered set which are closest to nums[i], and the minimum absolute difference between them is the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window with Sorted List | Time Complexity: O(n log x), where n is the length of the array and x is the constraint for indices apart. Space Complexity: O(x) due to storing the elements in the sorted list. |
| Brute Force with Constraint Check | Time Complexity: O(n^2), as all pairs are checked. Space Complexity: O(1), as only simple variables are used. |
| Ordered Set | — |
| 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 |
Leetcode Weekly contest 358 - Medium - Minimum Absolute Difference Between Elements With Constraint • Prakhar Agrawal • 2,651 views views
Watch 9 more video solutions →Practice Minimum Absolute Difference Between Elements With Constraint with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor