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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

1
2

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

Example 3

1
2

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

Solution

Method 1 – Binary Search on Sorted arr2

Intuition

For each element in arr1, we want to check if all elements in arr2 are at a distance greater than d. By sorting arr2, we can use binary search to efficiently check if there is any arr2[j] such that |arr1[i] - arr2[j]| <= d.

Approach

  1. Sort arr2.
  2. For each element x in arr1:
    • Use binary search to find the position where arr2[j] >= x - d.
    • Check if arr2[j] is within [x-d, x+d].
    • If no such arr2[j] exists, increment the answer.
  3. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (int x : arr1) {
            auto it = lower_bound(arr2.begin(), arr2.end(), x - d);
            if (it == arr2.end() || abs(*it - x) > d) {
                if (it == arr2.begin() || abs(*(it-1) - x) > d) ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
    sort.Ints(arr2)
    ans := 0
    for _, x := range arr1 {
        i := sort.SearchInts(arr2, x-d)
        ok := true
        if i < len(arr2) && abs(arr2[i]-x) <= d {
            ok = false
        }
        if i > 0 && abs(arr2[i-1]-x) <= d {
            ok = false
        }
        if ok {
            ans++
        }
    }
    return ans
}
func abs(a int) int { if a < 0 { return -a }; return a }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int x : arr1) {
            int i = Arrays.binarySearch(arr2, x - d);
            if (i < 0) i = -i - 1;
            boolean ok = true;
            if (i < arr2.length && Math.abs(arr2[i] - x) <= d) ok = false;
            if (i > 0 && Math.abs(arr2[i-1] - x) <= d) ok = false;
            if (ok) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findTheDistanceValue(arr1: IntArray, arr2: IntArray, d: Int): Int {
        arr2.sort()
        var ans = 0
        for (x in arr1) {
            val i = arr2.binarySearch(x - d).let { if (it < 0) -it - 1 else it }
            var ok = true
            if (i < arr2.size && kotlin.math.abs(arr2[i] - x) <= d) ok = false
            if (i > 0 && kotlin.math.abs(arr2[i-1] - x) <= d) ok = false
            if (ok) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
        from bisect import bisect_left
        arr2.sort()
        ans = 0
        for x in arr1:
            i = bisect_left(arr2, x - d)
            ok = True
            if i < len(arr2) and abs(arr2[i] - x) <= d:
                ok = False
            if i > 0 and abs(arr2[i-1] - x) <= d:
                ok = False
            if ok:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn find_the_distance_value(arr1: Vec<i32>, mut arr2: Vec<i32>, d: i32) -> i32 {
        arr2.sort();
        let mut ans = 0;
        for &x in &arr1 {
            let i = arr2.binary_search(&(x - d)).unwrap_or_else(|i| i);
            let mut ok = true;
            if i < arr2.len() && (arr2[i] - x).abs() <= d { ok = false; }
            if i > 0 && (arr2[i-1] - x).abs() <= d { ok = false; }
            if ok { ans += 1; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
        arr2.sort((a, b) => a - b);
        let ans = 0;
        for (const x of arr1) {
            let l = 0, r = arr2.length - 1, ok = true;
            while (l <= r) {
                const m = (l + r) >> 1;
                if (arr2[m] < x - d) l = m + 1;
                else r = m - 1;
            }
            if (l < arr2.length && Math.abs(arr2[l] - x) <= d) ok = false;
            if (l > 0 && Math.abs(arr2[l-1] - x) <= d) ok = false;
            if (ok) ans++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log m), where n = len(arr1), m = len(arr2), due to sorting and binary search for each element.
  • 🧺 Space complexity: O(1), ignoring the space for sorting arr2.