Skip to content

2817. Minimum Absolute Difference Between Elements With Constraint 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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