Code Logo

Find the Distance Value Between Two Arrays

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given two integer arrays arr1 and arr2, and an integer d, return the distance value between the two arrays. The distance value is defined as the number of elements arr1[i] such that there is no element arr2[j] satisfying |arr1[i] - arr2[j]| <= d.

A brute force double loop checks each arr1 element against all arr2 elements in O(n * m) time. Sorting arr2 and using binary search improves this to O((n + m) log m). For each element in arr1, binary search in arr2 to find the closest element (the insertion point). If the closest element on either side is within distance d, the element is invalid.

The insertion point is found by binary searching for arr1[i] in sorted arr2. The element at that index is the smallest element in arr2 that is >= arr1[i]. The element just before it (index - 1) is the largest element < arr1[i]. Only these two candidates need to be checked for the distance condition.

Edge cases include arr2 having a single element (only check that one), arr1[i] being smaller than all arr2 elements (only check the first), and arr1[i] being larger than all arr2 elements (only check the last).

The closest element in arr2 to any given x must be either the smallest arr2 element >= x or the largest arr2 element < x. Binary search for the insertion point gives us both candidates at once. Only these two need distance checking, not the entire arr2.

Example Input & Output

Example 1
Input
[1], [1,2,3], 2
Output
0
Explanation

1 is within distance 2 of arr2[0]=1.

Example 2
Input
[1,2,3], [1], 0
Output
2
Explanation

1 matches exactly (within 0). 2 and 3 are >0 from 1.

Example 3
Input
[2,1,100,3], [-5,-2,10,-3,7], 6
Output
1
Explanation

Only 100 is far enough from all.

Example 4
Input
[1,4,2,3], [-4,-3,6,10,20,30], 3
Output
2
Explanation

1,2,3 are within 3 of -4,-3; 4 within 3 of 6.

Example 5
Input
[4,5,8], [10,9,1,8], 2
Output
2
Explanation

5 and 8 are >2 away from all arr2; 4 is close to 1.

Algorithm Flow

Recommendation Algorithm Flow for Find the Distance Value Between Two Arrays
Recommendation Algorithm Flow for Find the Distance Value Between Two Arrays

Solution Approach

Sort arr2. For each x in arr1, binary search insertion point in arr2. Check closest left and right neighbors within distance d.

function solution(arr1, arr2, d) {
  arr2.sort(function(a, b) { return a - b; });
  var count = 0;
  for (var i = 0; i < arr1.length; i++) {
    var x = arr1[i];
    var lo = 0, hi = arr2.length - 1;
    var idx = arr2.length;
    while (lo <= hi) {
      var mid = Math.floor((lo + hi) / 2);
      if (arr2[mid] >= x) { idx = mid; hi = mid - 1; }
      else lo = mid + 1;
    }
    var valid = true;
    if (idx < arr2.length && Math.abs(x - arr2[idx]) <= d) valid = false;
    if (idx > 0 && Math.abs(x - arr2[idx - 1]) <= d) valid = false;
    if (valid) count++;
  }
  return count;
}

Time O((n+m) log m), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for (int x : arr1) {
            int lo = 0, hi = arr2.length - 1;
            int idx = arr2.length;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (arr2[mid] >= x) { idx = mid; hi = mid - 1; }
                else lo = mid + 1;
            }
            boolean valid = true;
            if (idx < arr2.length && Math.abs(x - arr2[idx]) <= d) valid = false;
            if (idx > 0 && Math.abs(x - arr2[idx - 1]) <= d) valid = false;
            if (valid) count++;
        }
        return count;
    }
}