1385. Find the Distance Value Between Two Arrays
- Array
- Two Pointers
- Binary Search
- Sorting
TIME
O((n + m) log m)
SPACE
O(m)
Intuition
arr1[i] counts when no arr2 value lies within d of it, which means the range [x - d, x + d] holds no arr2 value. Once arr2 is sorted, one binary search answers that: find the smallest value >= x - d and check whether it is still <= x + d.
Approach
- Sort
arr2. - For each
xinarr1, find the first indexiwitharr2[i] >= x - d. - Count
xifiis past the end orarr2[i] > x + d.
Complexity
- Time: O((n + m) log m), where
n = len(arr1)andm = len(arr2) - Space: O(1) beyond the sort (Python's sort uses O(m))
Edge Cases
d = 0:xfails only on an exact match- Every
arr2value is belowx - d: the search runs off the end, andxcounts - Every
arr2value is abovex + d: the search lands on index 0, the check fails, andxcounts - Duplicates in
arr1are counted separately, and duplicates inarr2change nothing - A value exactly
daway is within range, because the condition is<= d
Code
from bisect import bisect_left
class Solution:
def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
"""
1385. Find the Distance Value Between Two Arrays
Time: O((n + m) log m)
Space: O(m)
"""
arr2 = sorted(arr2)
m = len(arr2)
count = 0
for x in arr1:
# x counts when no arr2 value lies in [x - d, x + d].
i = bisect_left(arr2, x - d)
if i == m or arr2[i] > x + d:
count += 1
return countimport java.util.*;
/**
* 1385. Find the Distance Value Between Two Arrays
* Time: O((n + m) log m)
* Space: O(1)
*/
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int m = arr2.length, count = 0;
for (int x : arr1) {
// First index with arr2[i] >= x - d.
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (arr2[mid] < x - d) {
lo = mid + 1;
} else {
hi = mid;
}
}
// x counts when no arr2 value lies in [x - d, x + d].
if (lo == m || arr2[lo] > x + d) {
count++;
}
}
return count;
}
}