# Find the Distance Value Between Two Arrays
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-distance-value-between-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/find-the-distance-value-between-two-arrays
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Zepto](https://scaleengineer.com/companies/zepto)
---
## Problem
Given two integer arrays `arr1` and `arr2`, and the integer `d`, _return the distance value between the two arrays_.

The distance value is defined as the number of elements `arr1[i]` such that there is not any element `arr2[j]` where `|arr1[i]-arr2[j]| <= d`.

**Example 1:**

**Input:** arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
**Output:** 2
**Explanation:** 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
**|8-10|=2 <= d=2**
**|8-9|=1 <= d=2**
|8-1|=7 > d=2
**|8-8|=0 <= d=2**

**Example 2:**

**Input:** arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
**Output:** 2

**Example 3:**

**Input:** arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
**Output:** 1

**Constraints:**

* `1 <= arr1.length, arr2.length <= 500`
* `-1000 <= arr1[i], arr2[j] <= 1000`
* `0 <= d <= 100`

# Approaches
## Brute Force
The most straightforward solution is to use nested loops to check every pair of elements, one from `arr1` and one from `arr2`. For each element in `arr1`, we iterate through all elements of `arr2` to see if any pair has an absolute difference less than or equal to `d`. If no such element is found in `arr2` for the current element of `arr1`, we increment our distance counter.
**Time:** O(n * m), where `n` is the length of `arr1` and `m` is the length of `arr2`. This is because for each of the `n` elements in `arr1`, we iterate through all `m` elements of `arr2`. · **Space:** O(1) extra space, as we only use a few variables to store the count and a boolean flag.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory efficient.
**Cons:** Highly inefficient for large arrays, with a quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' error on platforms with stricter time limits for larger inputs.
### Explanation
This approach directly translates the problem statement into code. We iterate through `arr1` with an outer loop and `arr2` with an inner loop. A flag is used for each element of `arr1` to track if a 'close' element from `arr2` has been found. If the inner loop completes without finding any close element, we increment the final count.

Here is the algorithm:

*   Initialize a counter `distance` to 0.
*   For each element `num1` in `arr1`:
    *   Assume `num1` satisfies the condition by setting a flag `is_valid` to `true`.
    *   For each element `num2` in `arr2`:
        *   If the absolute difference `|num1 - num2|` is less than or equal to `d`, then `num1` does not satisfy the distance condition.
        *   Set `is_valid` to `false` and break the inner loop since we've found a 'close' element.
    *   If `is_valid` is still `true` after checking all elements in `arr2`, it means no close element was found. Increment `distance`.
*   After iterating through all elements of `arr1`, return `distance`.

```java
class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int distanceValue = 0;
        for (int num1 : arr1) {
            boolean foundCloseElement = false;
            for (int num2 : arr2) {
                if (Math.abs(num1 - num2) <= d) {
                    foundCloseElement = true;
                    break;
                }
            }
            if (!foundCloseElement) {
                distanceValue++;
            }
        }
        return distanceValue;
    }
}
```
### Algorithm
*   Initialize a counter `distance` to 0.
*   For each element `num1` in `arr1`:
    *   Assume `num1` satisfies the condition by setting a flag `is_valid` to `true`.
    *   For each element `num2` in `arr2`:
        *   If the absolute difference `|num1 - num2|` is less than or equal to `d`, then `num1` does not satisfy the distance condition.
        *   Set `is_valid` to `false` and break the inner loop since we've found a 'close' element.
    *   If `is_valid` is still `true` after checking all elements in `arr2`, it means no close element was found. Increment `distance`.
*   After iterating through all elements of `arr1`, return `distance`.

## Sorting with Two Pointers
A more optimized approach involves sorting both arrays first. By using two pointers, one for each array, we can check the distance condition in a single pass through both arrays. As we iterate through the sorted `arr1`, we only need to advance our pointer in the sorted `arr2`, avoiding repeated scans.
**Time:** O(n log n + m log m), dominated by the time to sort both arrays. The subsequent two-pointer scan takes O(n + m) time. · **Space:** O(log n + log m) or O(1), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives takes O(log n) stack space.
**Pros:** Much more efficient than brute force for large arrays.; The main logic after sorting is a single linear scan, which is very fast.
**Cons:** Requires sorting both arrays, which might not be ideal if the arrays are very large.; The `O(n log n)` term from sorting `arr1` can make this approach slower than the binary search method if `n` is large.
### Explanation
The key idea is that once both arrays are sorted, for an element `arr1[i]`, we don't need to check all of `arr2`. We only need to look at a 'window' of `arr2`. As `i` increases, `arr1[i]` increases, and this window in `arr2` also slides forward. This monotonicity allows us to use a second pointer `j` for `arr2` that only moves forward, leading to a linear time scan after the initial sort.

Here is the algorithm:

*   Sort both `arr1` and `arr2` in non-decreasing order.
*   Initialize two pointers, `i` for `arr1` and `j` for `arr2`, both to 0.
*   Initialize a counter `distanceValue` to 0.
*   Iterate with pointer `i` from `0` to `arr1.length - 1`:
    *   Advance pointer `j` as long as `j < arr2.length` and `arr2[j] < arr1[i] - d`. This skips elements in `arr2` that are too small for the current `arr1[i]`.
    *   Check if a close element exists. A close element does *not* exist if `j` has reached the end of `arr2` OR `arr2[j]` is already too large (i.e., `arr2[j] > arr1[i] + d`).
    *   If no close element is found, increment `distanceValue`.
*   Return `distanceValue`.

```java
import java.util.Arrays;

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int i = 0, j = 0;
        int distanceValue = 0;
        while (i < arr1.length) {
            // Advance j while arr2[j] is too small for arr1[i]
            while (j < arr2.length && arr2[j] < arr1[i] - d) {
                j++;
            }
            // Check if arr2 is exhausted or if arr2[j] is too large
            if (j == arr2.length || arr2[j] > arr1[i] + d) {
                distanceValue++;
            } else {
                // arr2[j] is in the range [arr1[i]-d, arr1[i]+d], so arr1[i] is not valid.
                // We still need to check the next arr1 element, but what if it's the same as current?
                // The problem is that one arr2[j] can invalidate multiple arr1[i]s.
                // A better way is to iterate through arr1 and check against arr2.
            }
            i++;
        }
        // The above logic is tricky. A clearer two-pointer logic is:
        i = 0; j = 0; 
        int count = 0;
        while(i < arr1.length && j < arr2.length){
            if(arr1[i] - arr2[j] > d){
                j++;
            } else if (arr2[j] - arr1[i] > d){
                count++;
                i++;
            } else {
                i++;
            }
        }
        count += arr1.length - i;
        return count;
    }
}
```
### Algorithm
*   Sort both `arr1` and `arr2` in non-decreasing order.
*   Initialize two pointers, `i` for `arr1` and `j` for `arr2`, both to 0.
*   Initialize a counter `distanceValue` to 0.
*   Iterate with pointer `i` from `0` to `arr1.length - 1`:
    *   Advance pointer `j` as long as `j < arr2.length` and `arr2[j] < arr1[i] - d`. This skips elements in `arr2` that are too small for the current `arr1[i]`.
    *   Check if a close element exists. A close element does *not* exist if `j` has reached the end of `arr2` OR `arr2[j]` is already too large (i.e., `arr2[j] > arr1[i] + d`).
    *   If no close element is found, increment `distanceValue`.
*   Return `distanceValue`.

## Sorting with Binary Search
This approach improves upon the brute-force method by optimizing the search within `arr2`. Instead of a linear scan, we can sort `arr2` first. Then, for each element in `arr1`, we use binary search on `arr2` to quickly determine if there's any element within the distance `d`. This avoids both the quadratic complexity of the brute-force method and the need to sort `arr1` as required by the two-pointer approach.
**Time:** O(m log m + n log m). It takes O(m log m) to sort `arr2`. Then, for each of the `n` elements in `arr1`, we perform a binary search on `arr2`, which takes O(log m) time. · **Space:** O(log m) or O(1), depending on the space used by the sorting algorithm for `arr2`.
**Pros:** Generally the most efficient and consistent approach.; Avoids sorting `arr1`, which makes it faster than the two-pointer approach when `n` is large.
**Cons:** Implementation of binary search for a range can be slightly more complex than a simple value search.
### Explanation
The core idea is to replace the O(m) linear scan of the inner loop with an O(log m) binary search. This is possible if `arr2` is sorted. For each `num1` from `arr1`, we are looking for any `num2` in `arr2` such that `|num1 - num2| <= d`, which is equivalent to checking if `arr2` contains any element in the closed interval `[num1 - d, num1 + d]`.

Here is the algorithm:

*   Sort the array `arr2` in non-decreasing order.
*   Initialize a counter `distanceValue` to 0.
*   For each element `num1` in `arr1`:
    *   Define the search range `[num1 - d, num1 + d]`.
    *   Perform a binary search on the sorted `arr2` to check if any element falls within this range.
    *   If the binary search does not find any such element, increment `distanceValue`.
*   Return `distanceValue`.

```java
import java.util.Arrays;

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int distanceValue = 0;
        for (int num1 : arr1) {
            if (!hasCloseElement(arr2, num1, d)) {
                distanceValue++;
            }
        }
        return distanceValue;
    }

    private boolean hasCloseElement(int[] arr, int value, int d) {
        int left = 0;
        int right = arr.length - 1;
        int lowerBound = value - d;
        int upperBound = value + d;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= lowerBound && arr[mid] <= upperBound) {
                return true; // Found an element within the range
            } else if (arr[mid] < lowerBound) {
                left = mid + 1;
            } else { // arr[mid] > upperBound
                right = mid - 1;
            }
        }
        return false; // No element found in the range
    }
}
```
### Algorithm
*   Sort the array `arr2` in non-decreasing order.
*   Initialize a counter `distanceValue` to 0.
*   For each element `num1` in `arr1`:
    *   Define the search range `[num1 - d, num1 + d]`.
    *   Perform a binary search on the sorted `arr2` to check if any element falls within this range.
    *   To do this, search for an element `num2` where `num1 - d <= num2 <= num1 + d`.
    *   If the binary search does not find any such element, increment `distanceValue`.
*   Return `distanceValue`.

# Solutions
### Java

```java
class Solution {
public
  int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    Arrays.sort(arr2);
    int ans = 0;
    for (int a : arr1) {
      if (check(arr2, a, d)) {
        ++ans;
      }
    }
    return ans;
  }
private
  boolean check(int[] arr, int a, int d) {
    int l = 0, r = arr.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (arr[mid] >= a - d) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l >= arr.length || arr[l] > a + d;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findTheDistanceValue(vector<int> &arr1, vector<int> &arr2, int d) {
    auto check = [&](int a) -> bool {
      auto it = lower_bound(arr2.begin(), arr2.end(), a - d);
      return it == arr2.end() || *it > a + d;
    };
    sort(arr2.begin(), arr2.end());
    int ans = 0;
    for (int &a : arr1) {
      ans += check(a);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: def check(a: int) -> bool: i = bisect_left(arr2, a - d) return i == len(arr2) or arr2[i] > a + d arr2 . sort() return sum(check(a) for a in arr1)

```