1385. Find the Distance Value Between Two Arrays
Problem Overview
An element of arr1 counts toward the distance value when every value in arr2 sits more than d away from it.
Intuition
An element of arr1 counts toward the distance value when every value in arr2 sits more than d away from it. Equivalently, the closed interval from a minus d to a plus d must contain no entry of arr2. Sorting arr2 once turns that check into a binary search. The insertion point of a is the first index whose value is at least a. Only that neighbor and the previous one can be the closest values in arr2, because every earlier entry is smaller and every later entry is larger. If both of those gaps are greater than d, then a is counted. The same test works when a is missing from arr2, because the bitwise complement of a negative BinarySearch result is the insertion index.
Algorithm
- 1Sort arr2 in nondecreasing order.
- 2For each value a in arr1, binary search for a in arr2 and turn a miss into its insertion index.
- 3Read the value at that index when it exists, and the value just before it when the index is positive.
- 4Count a when both of those gaps are greater than d.
- 5Return the count.
Example Walkthrough
Input: arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], d = 2
- 1.After sorting, arr2 is [1, 8, 9, 10].
- 2.For 4 the neighbors around the insertion point are 1 and 8. Both gaps are greater than 2, so 4 counts.
- 3.For 5 the same neighbors give gaps of 4 and 3, so 5 counts. For 8 the match at 8 has gap 0, so 8 is dropped.
Output: 2
Common Pitfalls
- •A gap of exactly d fails the test. The check is a strict greater than d.
- •When the insertion index is 0, there is no left neighbor to check.
- •When the insertion index equals the length of arr2, there is no right neighbor to check.
- •Sorting arr2 is enough. Sorting arr1 does not change the count.
// Approach: An element of arr1 counts when nothing in arr2 lies inside its
// closed interval of radius d. Sorting arr2 once lets each value from arr1
// binary search for its insertion point. Only that neighbor and the one
// before it can be the closest, so both gaps are checked against d.
// Time: O((m + n) log n) Space: O(1)
public class Solution {
public int FindTheDistanceValue(int[] arr1, int[] arr2, int d) {
Array.Sort(arr2);
int ans = 0;
foreach (int a in arr1) {
int i = Array.BinarySearch(arr2, a);
i = i < 0 ? ~i : i;
if ((i == arr2.Length || arr2[i] - a > d) &&
(i == 0 || a - arr2[i - 1] > d))
++ans;
}
return ans;
}
}