Watch 10 video solutions for Find the Distance Value Between Two Arrays, a easy level problem involving Array, Two Pointers, Binary Search. This walkthrough by onepunchcoder has 5,653 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given two integer arrays arr1 and arr2, and the 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 not any element arr2[j] where |arr1[i]-arr2[j]| <= d.
Example 1:
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 Output: 2 Explanation: For arr1[0]=4 we have: |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 For arr1[1]=5 we have: |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 For arr1[2]=8 we have: |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2
Example 2:
Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3 Output: 2
Example 3:
Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6 Output: 1
Constraints:
1 <= arr1.length, arr2.length <= 500-1000 <= arr1[i], arr2[j] <= 10000 <= d <= 100Problem Overview: You are given two integer arrays arr1 and arr2 and an integer d. The task is to count how many elements in arr1 have a distance greater than d from every element in arr2. In other words, for each value x in arr1, check that |x - y| > d for all values y in arr2. If that condition holds, the element contributes to the final count.
Approach 1: Brute Force Comparison (O(n * m) time, O(1) space)
The most direct method is to compare every element in arr1 with every element in arr2. For each arr1[i], iterate through arr2 and compute the absolute difference |arr1[i] - arr2[j]|. If any difference is less than or equal to d, the element is invalid and you stop checking further for that value. Otherwise, it contributes to the distance value. This approach relies purely on nested iteration over the array elements. It is easy to implement and works well when both arrays are small, but the quadratic comparison cost becomes expensive as input sizes grow.
Approach 2: Sorting + Binary Search (O(m log m + n log m) time, O(1) extra space)
A more efficient strategy is to first sort arr2. Once sorted, you can use binary search to quickly locate the closest element in arr2 for each value in arr1. For a given x, perform a binary search to find the insertion position in arr2. Then check the neighboring elements around that position to determine the smallest possible distance. If both neighbors have an absolute difference greater than d, the element qualifies. Sorting enables logarithmic lookups instead of scanning the entire array. The preprocessing cost is O(m log m) for sorting, and each query takes O(log m), producing a total runtime of O(m log m + n log m). This pattern often appears in problems combining sorting with fast lookups.
Recommended for interviews: Interviewers expect the sorting + binary search approach. The brute force solution demonstrates you understand the definition of the distance constraint and can implement the logic correctly. The optimized approach shows stronger algorithmic thinking by reducing repeated comparisons using ordering and logarithmic search. When arrays grow large, the difference between O(n * m) and O(n log m) becomes significant, which is exactly the optimization interviewers want to see.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n * m) | O(1) | Good for understanding the problem or when both arrays are very small |
| Sorting + Binary Search | O(m log m + n log m) | O(1) | Preferred for interviews and large inputs where scanning arr2 repeatedly is too slow |