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.
This approach involves iterating over each element in arr1 and checking the absolute differences with each element in arr2. If none of the elements in arr2 are within a distance d, we increase the count. This approach uses nested loops resulting in a time complexity of O(n*m).
This solution iterates through each element of arr1 and checks against all elements of arr2. If |arr1[i] - arr2[j]| > d for all j, it increments a counter.
Time Complexity: O(n*m), where n and m are the sizes of arr1 and arr2 respectively.
Space Complexity: O(1), since we are using only a fixed amount of extra space.
This approach first sorts arr2 and then uses binary search to quickly determine if there exists any element in arr2 within the distance d from any element in arr1. This significantly reduces the time complexity compared to the brute force approach.
This solution first sorts arr2. For each element in arr1, it performs a binary search in arr2 to check if there's an element that satisfies the condition. The sorting enables use of binary search to improve efficiency.
Time Complexity: O(m log m + n log m), where m is the size of arr2 due to sorting and binary searching, and n is the size of arr1.
Space Complexity: O(1), ignoring the space required for sorting.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n*m), where n and m are the sizes of |
| Optimized Approach with Sorting and Binary Search | Time Complexity: O(m log m + n log m), where m is the size of |
| 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 |
Leetcode 1385. Find the Distance Value Between Two Arrays (Easy) • onepunchcoder • 5,653 views views
Watch 9 more video solutions →Practice Find the Distance Value Between Two Arrays with our built-in code editor and test cases.
Practice on FleetCode