Find the Distance Value Between Two Arrays Easy Solution

Source: Dev.to

Problem Description

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 naïve solution would compare every element of arr1 with every element of arr2, which takes O(n × m) time.
To optimize this, we can sort arr2 and use binary search to quickly determine whether there exists an element in arr2 whose distance from a given arr1[i] is ≤ d. If such an element exists, arr1[i] cannot be counted.

Approach

1. Sort arr2 so binary search can be applied.
2. For each element arr1[i]:

   • Perform a binary search on arr2.

   • During the search, check if

     [ |,\text{arr2[mid]} - \text{arr1[i]},| \le d ]

   • If such an element is found, stop the search (the element is too close).

   • If the search finishes without finding any element within distance d, count arr1[i].

3. The count obtained after processing all elements of arr1 is the answer.

Binary Search Helper

The helper returns the index of an element in arr2 that is within distance d of the target, or -1 if none exists.

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
  Only a few variables are used: O(1).

Code

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

// Binary search to check if an element in arr2
// is within distance  {
  let left = 0;
  let right = arr.length - 1;

  while (left  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
    const idx = binarySearch(arr2, arr1[i], d);

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

  return count;
};

Illustrations