Code Implementation

class Solution:
    def findTheDistanceValue(self, arr1, arr2, d):
        arr2.sort()
        def is_far_enough(x):
            # Binary search for closest value in arr2 to x
            left, right = 0, len(arr2) - 1
            while left <= right:
                mid = (left + right) // 2
                if arr2[mid] < x:
                    left = mid + 1
                else:
                    right = mid - 1
            # Check neighbors for minimum distance
            candidates = []
            if right >= 0:
                candidates.append(abs(x - arr2[right]))
            if left < len(arr2):
                candidates.append(abs(x - arr2[left]))
            return all(c > d for c in candidates)
        return sum(is_far_enough(x) for x in arr1)
      

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int res = 0;
        for (int x : arr1) {
            auto it = lower_bound(arr2.begin(), arr2.end(), x);
            bool valid = true;
            if (it != arr2.end() && abs(*it - x) <= d) valid = false;
            if (it != arr2.begin() && abs(*(it - 1) - x) <= d) valid = false;
            if (valid) res++;
        }
        return res;
    }
};
      

import java.util.*;
class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for (int x : arr1) {
            int idx = Arrays.binarySearch(arr2, x);
            boolean valid = true;
            if (idx < 0) idx = -idx - 1;
            if (idx < arr2.length && Math.abs(arr2[idx] - x) <= d) valid = false;
            if (idx - 1 >= 0 && Math.abs(arr2[idx - 1] - x) <= d) valid = false;
            if (valid) count++;
        }
        return count;
    }
}
      

var findTheDistanceValue = function(arr1, arr2, d) {
    arr2.sort((a, b) => a - b);
    function isFarEnough(x) {
        let left = 0, right = arr2.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (arr2[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        let candidates = [];
        if (right >= 0) candidates.push(Math.abs(x - arr2[right]));
        if (left < arr2.length) candidates.push(Math.abs(x - arr2[left]));
        return candidates.every(c => c > d);
    }
    let res = 0;
    for (let x of arr1) {
        if (isFarEnough(x)) res++;
    }
    return res;
};
      

Problem Description

Given two integer arrays arr1 and arr2, and an integer d, you need to find the "distance value" between the two arrays. The distance value is defined as the number of elements x in arr1 such that for every element y in arr2, the absolute difference |x - y| is greater than d.

• You must count how many elements in arr1 are "far enough" from all elements in arr2 (i.e., not within distance d of any element in arr2).
• Each element in arr1 is considered independently.
• There is no requirement to avoid reusing elements; the comparison is made for each x in arr1 against all y in arr2.

Thought Process

To solve this problem, the initial thought is to check, for every element in arr1, whether it is "too close" to any element in arr2. If it is not, we count it as a valid result.

The brute-force approach would be to use two nested loops: for each element in arr1, compare it to every element in arr2 and check if the absolute difference is less than or equal to d. If none of the comparisons are within distance d, we increment our count.

However, this approach could be slow for large arrays (O(N*M) time complexity, where N and M are the lengths of the arrays). We can optimize by noticing that if arr2 is sorted, we can use binary search to quickly find the closest value(s) to x in arr2 and only check those, reducing the number of comparisons per x from O(M) to O(log M).

Solution Approach

• Step 1: Sort arr2
  • Sorting allows us to use binary search for efficient proximity checks.
• Step 2: For each element x in arr1, use binary search to find the closest element(s) in arr2
  • Use a standard binary search to locate the index where x would be inserted in arr2.
  • Check the neighbor(s) at this index and the previous index, as these are the closest possible values to x.
• Step 3: Check if |x - y| > d for all neighbor candidates
  • If all candidates are at a distance greater than d, increment the count.
• Step 4: Return the count
  • The final count is the answer: the distance value between the two arrays.

This approach reduces the time complexity per element in arr1 from O(M) to O(log M), making it efficient for large arrays.

Example Walkthrough

Let's say arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], and d = 2.

1. Sort arr2: [1, 8, 9, 10]
2. Check x = 4:
   • Binary search: 4 would be inserted at index 1 (between 1 and 8).
   • Check arr2[0] = 1: |4-1| = 3 > 2
   • Check arr2[1] = 8: |4-8| = 4 > 2
   • Both distances are greater than d, so count += 1.
3. Check x = 5:
   • Binary search: 5 would be inserted at index 1.
   • Check arr2[0] = 1: |5-1| = 4 > 2
   • Check arr2[1] = 8: |5-8| = 3 > 2
   • Both distances are greater than d, so count += 1.
4. Check x = 8:
   • Binary search: 8 is at index 1.
   • Check arr2[1] = 8: |8-8| = 0 ≤ 2 (too close)
   • At least one value is too close, so do not increment count.
5. Final count: 2

So, the output is 2.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N*M), where N is the length of arr1 and M is the length of arr2.
  • Space Complexity: O(1), as no extra space is used except for counters and loop variables.
• Optimized approach (with sorting and binary search):
  • Time Complexity: O(M log M + N log M)
    • O(M log M) for sorting arr2.
    • O(N log M) for N binary searches (one for each element in arr1).
  • Space Complexity: O(1) or O(M) depending on the sorting algorithm used (most languages sort in-place).

Summary

The key to solving the "Find the Distance Value Between Two Arrays" problem efficiently is to realize that you only need to check the closest elements in arr2 for each element in arr1. By sorting arr2 and using binary search, you can quickly determine whether any element in arr2 is within distance d of a given arr1 element. This optimization reduces the time complexity significantly and makes the solution scalable for larger arrays.