Find the Distance Value Between Two Arrays: Binary Search Approach

May 29, 20266 min read

leetcodeproblemeasyarraysbinary-searchsorting

Given two integer arrays arr1 and arr2 and an 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 no element arr2[j] where |arr1[i] - arr2[j]| <= d. In other words, count every element in arr1 whose closest neighbor in arr2 is more than d away. This is LeetCode 1385: Find the Distance Value Between Two Arrays.

arr1=[4,5,8], arr2=[10,9,1,8], d=2. For each arr1 element, check if any arr2 element is within distance d. Elements 4 and 5 pass. Element 8 fails because arr2 contains 8.

Why this problem matters

This problem is a clean introduction to combining sorting with binary search to answer proximity queries. The brute force approach checks every pair of elements across both arrays, but sorting arr2 first lets you answer "is any element within distance d?" in logarithmic time per query. That pattern, sorting one collection and binary searching into it for each element of another, appears constantly in interval problems, closest-pair problems, and two-pointer variations. Getting comfortable with it here makes harder problems feel familiar.

The key insight

Sort arr2. For each element in arr1, use binary search to find where it would be inserted in sorted arr2. The closest element in arr2 must be either the one just before or just after that insertion point. If both neighbors are more than d away, the element counts toward the distance value.

This reduces the per-element check from O(n) (scanning all of arr2) to O(log n) (one binary search). Since you do this for every element in arr1, the total time becomes O((m + n) log n) instead of O(m * n).

The solution

from bisect import bisect_left

def find_the_distance_value(arr1: list[int], arr2: list[int], d: int) -> int:
    arr2.sort()
    count = 0

    for val in arr1:
        pos = bisect_left(arr2, val)
        left_ok = pos == 0 or abs(val - arr2[pos - 1]) > d
        right_ok = pos == len(arr2) or abs(val - arr2[pos]) > d

        if left_ok and right_ok:
            count += 1

    return count

The function sorts arr2 once, then iterates through arr1. For each value, bisect_left finds the insertion index in sorted arr2. We then check the two candidates for the closest element: the one at pos - 1 (the largest value smaller than or equal to val) and the one at pos (the smallest value greater than or equal to val). Boundary checks handle the case where pos is 0 (nothing to the left) or len(arr2) (nothing to the right). If both neighbors are farther than d, we increment the count.

The bisect_left function returns the leftmost position where val could be inserted while keeping arr2 sorted. The closest element to val in arr2 is always at pos or pos - 1. You never need to check more than these two positions, because everything farther away in the sorted array is guaranteed to be even farther from val.

Practice binary search patterns with spaced repetition

Visual walkthrough

Step 1: Sort arr2

Sorting arr2 lets us use binary search to find the closest element in O(log n) time instead of scanning every element.

arr2 sorted: [1, 8, 9, 10]

Step 2: Check arr1[0] = 4

Binary search in sorted arr2 for the value closest to 4. The insertion point falls between 1 and 8. Check both neighbors.

|4 - 1| = 3 > d=2, and |4 - 8| = 4 > d=2. No element within d. Count it. Running total: 1

Step 3: Check arr1[1] = 5

Binary search in sorted arr2 for the value closest to 5. The insertion point again falls between 1 and 8.

|5 - 8| = 3 > d=2, and |5 - 1| = 4 > d=2. No element within d. Count it. Running total: 2

Step 4: Check arr1[2] = 8

Binary search finds an exact match at index 1 in sorted arr2.

|8 - 8| = 0, which is not > d=2. An element is within d. Do not count. Running total: 2

Step 5: Final result

We checked all three elements in arr1. Two of them had no arr2 neighbor within distance d.

Distance value = 2. Elements 4 and 5 (green) counted. Element 8 (red) did not count.

Sorting arr2 turns the proximity check into a simple binary search. For each element in arr1, you land at the insertion point and peek left and right. If neither neighbor is within d, that element counts. The logic is the same every time, just a sort followed by repeated binary searches.

Complexity analysis

Approach	Time	Space
Sort + binary search	O((m + n) log n)	O(1)

Here m = len(arr1) and n = len(arr2).

Time: Sorting arr2 takes O(n log n). For each of the m elements in arr1, we perform one binary search in O(log n). Total: O(n log n + m log n) = O((m + n) log n).

Space: Sorting arr2 in place uses O(1) extra space (ignoring the sort's internal stack). We only store a counter and a few variables.

The building blocks

1. Binary search for closest element

The core building block is using bisect_left to find where a value would sit in a sorted array, then checking the neighbors at pos - 1 and pos. This pattern answers "what is the closest value in this sorted collection?" in O(log n) time.

from bisect import bisect_left

def closest_in_sorted(arr, val):
    pos = bisect_left(arr, val)
    candidates = []
    if pos > 0:
        candidates.append(arr[pos - 1])
    if pos < len(arr):
        candidates.append(arr[pos])
    return min(candidates, key=lambda x: abs(x - val))

You do not always need the actual closest value. Sometimes, like in this problem, you only need to know whether the closest is within a threshold. But the lookup pattern is identical: find the insertion point, check both sides.

2. Distance threshold check

Once you know how to find the closest element, the threshold check is a thin wrapper. You check whether both the left neighbor and the right neighbor exceed the distance d. If either is within d, the element fails. If both exceed d (or do not exist), it passes.

def is_far_enough(sorted_arr, val, d):
    pos = bisect_left(sorted_arr, val)
    if pos > 0 and abs(val - sorted_arr[pos - 1]) <= d:
        return False
    if pos < len(sorted_arr) and abs(val - sorted_arr[pos]) <= d:
        return False
    return True

This check runs in O(log n) per call. Wrapping it in a loop over arr1 gives you the full solution.

Drill binary search building blocks

Edge cases

All elements count: if arr2 is empty or every element in arr2 is far from every element in arr1, the distance value equals len(arr1).
No elements count: if every element in arr1 has a neighbor in arr2 within d, the distance value is 0.
d = 0: only exact matches disqualify an element. If arr1[i] does not appear in arr2, it counts.
Single-element arrays: the binary search still works correctly with one element. bisect_left returns 0 or 1, and the boundary checks handle both cases.
Duplicate values: duplicates in arr2 do not affect correctness. bisect_left lands at the first occurrence, and the neighbor check still finds the closest.
Negative numbers: the absolute value comparison handles negatives without any special cases.

From understanding to recall

You have seen how sorting and binary search turn an O(m * n) brute force into an O((m + n) log n) solution. The logic is clean: sort, binary search, check two neighbors. But reproducing it under interview pressure is different from reading it here.

The details that trip people up: remembering to check both pos - 1 and pos, handling boundary conditions when pos is 0 or len(arr2), and recalling that bisect_left gives the insertion point for the leftmost position. These small details matter when the clock is ticking.

Spaced repetition drills these details until they are automatic. You write the sort, the binary search, and the neighbor check from scratch at increasing intervals. After a few rounds, the pattern flows without hesitation. You do not re-derive it. You just write it.