2817. Minimum Absolute Difference Between Elements With Constraint LeetCode Solution
In this guide, you will get 2817. Minimum Absolute Difference Between Elements With Constraint LeetCode Solution with the best time and space complexity. The solution to Minimum Absolute Difference Between Elements With Constraint problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Absolute Difference Between Elements With Constraint
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.
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.
2817. Minimum Absolute Difference Between Elements With Constraint LeetCode Solution in C++
class Solution {
public:
int minAbsoluteDifference(vector<int>& nums, int x) {
int ans = INT_MAX;
set<int> seen;
for (int i = x; i < nums.size(); ++i) {
seen.insert(nums[i - x]);
// `upper_bound` works as well.
const auto it = seen.lower_bound(nums[i]);
if (it != seen.cend())
ans = min(ans, *it - nums[i]);
if (it != seen.cbegin())
ans = min(ans, nums[i] - *prev(it));
}
return ans;
}
}; /* code provided by PROGIEZ */
2817. Minimum Absolute Difference Between Elements With Constraint LeetCode Solution in Java
class Solution {
public int minAbsoluteDifference(List<Integer> nums, int x) {
int ans = Integer.MAX_VALUE;
TreeSet<Integer> seen = new TreeSet<>();
for (int i = x; i < nums.size(); ++i) {
seen.add(nums.get(i - x));
Integer hi = seen.ceiling(nums.get(i));
if (hi != null)
ans = Math.min(ans, hi - nums.get(i));
Integer lo = seen.floor(nums.get(i));
if (lo != null)
ans = Math.min(ans, nums.get(i) - lo);
}
return ans;
}
} // code provided by PROGIEZ
2817. Minimum Absolute Difference Between Elements With Constraint LeetCode Solution in Python
from sortedcontainers import SortedSet
class Solution:
def minAbsoluteDifference(self, nums: list[int], x: int) -> int:
ans = math.inf
seen = SortedSet()
for i in range(x, len(nums)):
seen.add(nums[i - x])
it = seen.bisect_left(nums[i])
if it != len(seen):
ans = min(ans, seen[it] - nums[i])
if it != 0:
ans = min(ans, nums[i] - seen[it - 1])
return ans # code by PROGIEZ
