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

Solution Approach

Given two arrays arr1 and arr2, find the number of elements in arr1 that have no element in arr2 within distance d. For each element in arr1, check all elements in arr2. If any element in arr2 is within d, skip it. Count elements in arr1 where no close element exists in arr2.

function findTheDistanceValue(arr1, arr2, d) {
  var count = 0;
  for (var i = 0; i < arr1.length; i++) {
    var valid = true;
    for (var j = 0; j < arr2.length; j++) {
      if (Math.abs(arr1[i] - arr2[j]) <= d) { valid = false; break; }
    }
    if (valid) count++;
  }
  return count;
}

Brute force is acceptable since constraints are small. Sorting arr2 and using binary search for the closest value would improve performance for larger inputs.

Time complexity is O(n*m), space complexity is 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;
    }
}