Find the Distance Value Between Two Arrays Easy Solution

The problem asks us to count how many elements in arr1 are far enough from every element in arr2.

For an element x in arr1, we must check that:

[
|x - y| > d
]

for every element y in arr2.

A simple way would be to compare every element of arr1 with every element of arr2, but that would take O(n × m) time.

To optimize this, we can sort arr2 and use Binary Search.
Binary search helps us quickly check if there exists an element in arr2 whose distance from arr1[i] is less than or equal to d.

If such an element exists, then the element from arr1 cannot be counted.

---

Approach

1. Sort arr2 so we can apply binary search.
2. For every element arr1[i]:

• Use binary search on arr2.
• During the search, check if

[
|arr2[mid] - arr1[i]| \le d
]

1. If such an element is found, return its index immediately.
2. If the search ends without finding such an element, return -1.
3. In the main function:

• If binary search returns -1, it means no element in arr2 is within distance d.
• Increase the count.

This reduces unnecessary comparisons and improves efficiency.

---

Complexity

Time complexity

• Sorting arr2 → O(n log n)
• Binary search for each element of arr1 → O(m log n)

Overall:

[
O(n \log n + m \log n)
]

---

Space complexity

No extra data structures are used apart from variables.

[
O(1)
]

---

Code

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number} d
 * @return {number}
 */

// Binary search to check if an element in arr
// is within distance <= d from target
let BinarySearch = (arr, target, d) => {
  let Left = 0
  let Right = arr.length - 1

  while (Left <= Right) {
    let mid = Math.floor((Left + Right) / 2)

    // If distance is within d, target is too close
    if (Math.abs(arr[mid] - target) <= d) {
      return mid
    }

    // Standard binary search movement
    if (arr[mid] > target) {
      Right = mid - 1
    } else {
      Left = mid + 1
    }
  }

  // No element within distance d
  return -1
}

var findTheDistanceValue = function(arr1, arr2, d) {

  // Sort arr2 for binary search
  arr2.sort((a,b)=> a - b)

  let count = 0

  for(let i = 0 ; i < arr1.length ; i++){

    // Check if arr1[i] is close to any element in arr2
    let el = BinarySearch(arr2 , arr1[i] , d)

    // If no close element found, count it
    if(el === -1){
      count++
    }

  }

  return count
};

---