1385. Find the Distance Value Between Two Arrays

Approach 1: Binary Search

• Time: $O(\max(|\texttt{arr1}|, |\texttt{arr2}|)\log |\texttt{arr2}|)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    int ans = 0;

    ranges::sort(arr2);

    for (const int a : arr1) {
      const auto it = lower_bound(begin(arr2), end(arr2), a);
      if ((it == arr2.end() || *it - a > d) &&
          (it == arr2.begin() || a - *prev(it) > d))
        ++ans;
    }

    return ans;
  }
};

class Solution {
  public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    int ans = 0;

    Arrays.sort(arr2);

    for (final int a : arr1) {
      int i = Arrays.binarySearch(arr2, a);
      i = i < 0 ? -i - 1 : i;
      if ((i == arr2.length || arr2[i] - a > d) && (i == 0 || a - arr2[i - 1] > d))
        ++ans;
    }

    return ans;
  }
}

class Solution:
  def findTheDistanceValue(
      self,
      arr1: list[int],
      arr2: list[int],
      d: int,
  ) -> int:
    ans = 0

    arr2.sort()

    for a in arr1:
      i = bisect.bisect_left(arr2, a)
      if ((i == len(arr2) or arr2[i] - a > d) and
              (i == 0 or a - arr2[i - 1] > d)):
        ans += 1

    return ans

Approach 2: Heuristic

• Time: $O(\max(|\texttt{arr1}|, |\texttt{arr2}|)\log |\texttt{arr2}|)$
• Space: $O(1)$

C++

class Solution {
 public:
  int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    int ans = 0;

    ranges::sort(arr2);

    for (const int a : arr1)
      if (ranges::upper_bound(arr2, a + d) == ranges::lower_bound(arr2, a - d))
        ++ans;

    return ans;
  }
};