Find the Distance Value Between Two Arrays

Language Options

Problem Description

So, you think you can find the distance value between two arrays? Well, let me tell you, it’s not as easy as finding your car keys when you’re running late for work! The problem is simple yet tricky: given two arrays, arr1 and arr2, and a distance value d, you need to find out how many elements in arr1 have no element in arr2 that is within the distance d.

Imagine you’re at a party, and you want to find out how many of your friends are standing far enough away that you can’t hear their embarrassing stories. If they’re too close (within distance d), you can’t count them!

Code Solution


class Solution {
  public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    int ans = 0;

    Arrays.sort(arr2);

    for (final int a : arr1) {
      int i = Arrays.binarySearch(arr2, a);
      i = i < 0 ? -i - 1 : i;
      if ((i == arr2.length || arr2[i] - a > d) && (i == 0 || a - arr2[i - 1] > d))
        ++ans;
    }

    return ans;
  }
}

Approach

The approach taken in this solution is quite clever. First, we sort arr2 to make it easier to find elements that are within the distance d. Then, for each element in arr1, we use binary search to find the closest element in arr2. If the closest element is too close (within distance d), we skip counting that element. If both the closest element and the one before it are too close, we also skip counting. If neither is too close, we increment our answer.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n + m log m), where `n` is the length of `arr1` and `m` is the length of `arr2`.
Space Complexity	O(1), as we are using a constant amount of space for variables.

Real-World Example

Let’s say you’re at a concert, and you want to find out how many people are standing far enough away from you that you can enjoy the music without hearing their off-key singing. If someone is within a certain distance (let’s say d), you can’t count them as “far enough.” This problem is just like that! You’re trying to find out how many of your friends are far enough away to avoid their terrible singing.