Find the Distance Value Between Two Arrays

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 lost socks in the laundry! The problem is simple yet tricky: given two arrays, arr1 and arr2, and a non-negative integer 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 might just have to endure the cringe!

Code Solution


class Solution {
 public:
  int findTheDistanceValue(vector& arr1, vector& arr2, int d) {
    int ans = 0;

    ranges::sort(arr2);

    for (const int a : arr1) {
      const auto it = lower_bound(begin(arr2), end(arr2), a);
      if ((it == arr2.end() || *it - a > d) &&
          (it == arr2.begin() || a - *prev(it) > d))
        ++ans;
    }

    return ans;
  }
};

Approach

The approach here is quite elegant. First, we sort arr2 to make it easier to find elements that are within the distance d. For each element in arr1, we use lower_bound to find the position in arr2 where the current element would fit. We then check if the closest elements in arr2 are within the distance d. If both the closest elements are too far away, we increment our answer.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n + m log m), where `n` is the size of `arr1` and `m` is the size of `arr2`. The sorting step dominates the complexity.
Space Complexity	O(1) if we ignore the space used by the input arrays.

Real-World Example

Let’s say you’re organizing a marathon, and you want to ensure that no two runners are too close to each other at the starting line. You can think of arr1 as the positions of the runners and arr2 as the positions of the cones marking the distance. If a runner is too close to a cone (within distance d), they might trip over it!