Is Find the Distance Value Between Two Arrays easy or hard?

The problem is classified as Easy on LeetCode with an acceptance rate above 70%. The brute force logic is straightforward, but recognizing that sorting arr2 enables faster binary searches is the key optimization that improves performance.

Find the Distance Value Between Two Arrays Python/Java solution

In Python or Java, the optimized solution sorts arr2 and uses built-in binary search utilities such as bisect in Python or Arrays.binarySearch in Java. After locating the insertion index, you check adjacent elements to confirm the distance constraint before counting the element.

How to solve Find the Distance Value Between Two Arrays in O(n log m)?

First sort arr2. For each element x in arr1, run a binary search to find the closest position in arr2 where x could be inserted. Check the neighbor values around that index and compute the absolute difference. If both neighbors differ from x by more than d, count the element.

What is the best approach for Find the Distance Value Between Two Arrays?

The most efficient approach sorts arr2 and then performs binary search for each element in arr1. After sorting, you locate the closest value in arr2 and check whether the absolute difference is greater than d. This reduces repeated comparisons and runs in O(m log m + n log m) time with constant extra space.

Is Find the Distance Value Between Two Arrays asked at Google/Amazon/Meta?

Problems combining arrays with binary search patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear verbatim, the technique of sorting one array and searching for closest values is a common interview pattern.

What data structure is used in Find the Distance Value Between Two Arrays?

The problem mainly uses arrays along with algorithmic techniques like sorting and binary search. No advanced data structures are required. The key idea is leveraging the sorted order of arr2 to quickly find the nearest values for comparison.

What is the time complexity of Find the Distance Value Between Two Arrays?

The brute force solution takes O(n * m) time because every element in arr1 is compared with every element in arr2. The optimized approach sorts arr2 in O(m log m) and then performs binary search for each element of arr1 in O(log m), giving a total time complexity of O(m log m + n log m).

Description Hints 1 Solution Video 12:30

1385. Find the Distance Value Between Two Arrays

Easy72.1% acceptance5 companies

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] <= 1000
0 <= d <= 100

Asked at 5 companies

Zepto Uber

Google Microsoft Bloomberg

Topics

Hints open one at a time

Hint 1

Sort 'arr2' and use binary search to get the closest element for each 'arr1[i]', it gives a time complexity of O(nlogn).

12:30

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[4,5,8]
[10,9,1,8]
2

Input

[1,4,2,3]
[-4,-3,6,10,20,30]
3

Input

[2,1,100,3]
[-5,-2,10,-3,7]
6

Your code is saved on this device.Solution