Find the Distance Value Between Two Arrays

easy two pointers sorting binary search

Problem

You are given two integer arrays arr1 and arr2 and an integer d. The distance value is the number of elements arr1[i] for which there is no element arr2[j] satisfying |arr1[i] − arr2[j]| ≤ d. Return that count.

Inputarr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], d = 2

Output2

For 4, the nearest arr2 value is 1 (distance 3) — safe. For 5, the nearest is 8 (distance 3) — safe. For 8, arr2 contains 8 (distance 0) and 9 (distance 1), both ≤ 2 — not counted. So 2 elements qualify.

arr1 (comma-separated)

arr2 (comma-separated)

def find_the_distance_value(arr1, arr2, d):
    arr2.sort()
    count = 0
    for x in arr1:
        lo, hi = 0, len(arr2)
        while lo < hi:
            mid = (lo + hi) // 2
            if arr2[mid] < x - d:
                lo = mid + 1
            else:
                hi = mid
        if lo == len(arr2) or arr2[lo] > x + d:
            count += 1
    return count

function findTheDistanceValue(arr1, arr2, d) {
  arr2.sort((a, b) => a - b);
  let count = 0;
  for (const x of arr1) {
    let lo = 0, hi = arr2.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr2[mid] < x - d) lo = mid + 1;
      else hi = mid;
    }
    if (lo === arr2.length || arr2[lo] > x + d) count++;
  }
  return count;
}

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for (int x : arr1) {
            int lo = 0, hi = arr2.length;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (arr2[mid] < x - d) lo = mid + 1;
                else hi = mid;
            }
            if (lo == arr2.length || arr2[lo] > x + d) count++;
        }
        return count;
    }
}

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    sort(arr2.begin(), arr2.end());
    int count = 0;
    for (int x : arr1) {
        int lo = 0, hi = (int)arr2.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr2[mid] < x - d) lo = mid + 1;
            else hi = mid;
        }
        if (lo == (int)arr2.size() || arr2[lo] > x + d) count++;
    }
    return count;
}

Explanation

The brute-force idea is simple: for every element x in arr1, scan all of arr2 and check if any value lands within distance d of x. If none does, x counts. That is O(n·m) work, which is fine for tiny inputs but wasteful when the arrays grow.

The key observation is that "is there any value within [x − d, x + d]?" is a range question, and range questions become cheap once the data is sorted. So we first sort arr2.

For a fixed x, every forbidden value lies in the closed window [x − d, x + d]. We binary-search for the first element of arr2 that is ≥ x − d — that is the leftmost candidate that could possibly fall inside the window. Call its index lo. If lo runs off the end of the array, or the value sitting there is already > x + d, then nothing lies inside the window and x is safe, so we increment the count.

Walk the example with d = 2 and sorted arr2 = [1, 8, 9, 10]. For x = 4 the window is [2, 6]; the first value ≥ 2 is 8, which is above 6, so 4 is safe. For x = 5 the window is [3, 7]; again the first value ≥ 3 is 8 > 7, so 5 is safe. For x = 8 the window is [6, 10]; the first value ≥ 6 is 8, which sits inside the window, so 8 is not safe. Total safe count = 2.

Because each lookup is a binary search over the sorted array, the per-element cost drops from O(m) to O(log m).

Time: O((n + m) log m) Space: O(1)