1385. Find the Distance Value Between Two Arrays

1. Description

Given integer arrays arr1 and arr2 and a non-negative integer d, count the elements of arr1 whose absolute difference from every element of arr2 is strictly greater than d.
Return this count as the distance value between the arrays. Count repeated occurrences in arr1 separately.

2. Example

Example 1

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: Both 4 and 5 are more than 2 away from every value in arr2. The value 8 fails because arr2 contains 8.

Example 2

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2
Explanation: Only 1 and 2 satisfy the required distance from every value in arr2.

Example 3

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1
Explanation: Only 100 has an absolute difference greater than 6 from every value in arr2.

3. Constraints

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

4. Solutions

Binary Search

m = arr1.size(), n = arr2.size()
Time complexity: O(n log n + m log(n + 1))
Space complexity: O(log n)

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

class Solution {
public:
    int findTheDistanceValue(vector<int> &arr1, vector<int> &arr2, int d) {
        sort(arr2.begin(), arr2.end());

        int count = 0;
        for (int num : arr1) {
            auto iter = lower_bound(arr2.begin(), arr2.end(), num - d);
            if (iter == arr2.end() || *iter > num + d) {
                ++count;
            }
        }

        return count;
    }
};