340. Find the Distance Value Between Two Arrays

Sort arr2 once, then for each value in arr1 jump straight to its nearest neighbour in arr2 — if even the closest element is farther than d, nothing in arr2 is within range.

Idea

An element arr1[i] counts toward the distance value only when every element of arr2 is strictly farther than d from it. Checking all pairs is O(n * m). The key observation: once arr2 is sorted, the element closest to arr1[i] sits right next to the position where arr1[i] would be inserted. If that closest neighbour is already more than d away, every other element is even farther, so we only ever need to look at the two neighbours surrounding the insertion point.

Walk-through

Take arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2.

1. Sort arr2 → [1,8,9,10]. We now do all lookups against this sorted array.
2. x = 4. Binary-search for 4 → insertion index 1 (between 1 and 8). Left neighbour 1: 4 - 1 = 3 > 2. Right neighbour 8: 8 - 4 = 4 > 2. Both farther than d, so 4 counts. Running total = 1.
3. x = 5. Insertion index 1. Left neighbour 1: 5 - 1 = 4 > 2. Right neighbour 8: 8 - 5 = 3 > 2. Both far → 5 counts. Total = 2.
4. x = 8. Insertion index 1 (8 lands before the existing 8). Right neighbour 8: 8 - 8 = 0 <= 2. A match exists, so 8 does NOT count.
5. Answer = 2.

Why two neighbours are enough

In a sorted array the values increase left to right, so the element with the smallest absolute difference from x is whichever of the two values straddling x's insertion point is closer. If both of those are more than d away, no element can be within d.

Complexity

• Time: O((n + m) log m) — sort arr2 in O(m log m), then one O(log m) binary search per element of arr1.
• Space: O(1) extra (sorting in place), ignoring the sort's own scratch space.

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for (int x : arr1) {
            int pos = lowerBound(arr2, x);
            boolean close = false;
            if (pos < arr2.length && arr2[pos] - x <= d) close = true;
            if (pos > 0 && x - arr2[pos - 1] <= d) close = true;
            if (!close) count++;
        }
        return count;
    }

    private int lowerBound(int[] a, int key) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < key) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}