Find the Distance Value Between Two Arrays — Solution
Find the Distance Value Between Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Distance Value Between Two Arrays is an easy coding problem on arrays, binary search and two pointers, asked in Amazon, TCS and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Binary Search, Two Pointers
- Asked at: Amazon, TCS, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The distance value is the number of elements a in arr1 for which there is no element b in arr2 with |a - b| <= d.
Return the distance value.
Example 1
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: Only 8 has a neighbour within 2 (namely 8 and 9).
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 <= 100
Hints for Find the Distance Value Between Two Arrays
Hint 1
The direct double loop is
O(n·m)and fine at these sizes.Hint 2
The faster route sorts
arr2and binary searches for the nearest value to eacha.Hint 3
Only the closest element on each side can violate the condition.
How to solve Find the Distance Value Between Two Arrays
An element of arr1 survives when the whole of arr2 stays strictly further than d away from it. Checking that directly is a nested scan; sorting arr2 lets a binary search test only the two nearest candidates.
Approach
- For each
ainarr1, scanarr2for anybwith|a - b| <= d. - Count
awhen no suchbexists. - To speed it up: sort
arr2, binary search fora, and test only the neighbour on each side.
Why it works
If any element of arr2 lies within d of a, the closest one does — so testing the immediate predecessor and successor in sorted order is exhaustive.
Complexity
- Time —
O(n · m), or O((n + m) log m) with sorting - Space —
O(1)
Pitfalls
<= dis inclusive, so a difference of exactlyddisqualifies the element.- Counting elements of
arr2rather thanarr1answers the mirror question. - Negative values mean the absolute difference is essential.
Reference solution
Python
from typing import List
def findTheDistanceValue(arr1: List[int], arr2: List[int], d: int) -> int:
return sum(1 for a in arr1 if all(abs(a - b) > d for b in arr2))Java
public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int total = 0;
for (int a : arr1) {
boolean ok = true;
for (int b : arr2) {
if (Math.abs(a - b) <= d) { ok = false; break; }
}
if (ok) total++;
}
return total;
}C++
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
int total = 0;
for (int a : arr1) {
bool ok = true;
for (int b : arr2) {
if (abs(a - b) <= d) { ok = false; break; }
}
if (ok) total++;
}
return total;
}JavaScript
var findTheDistanceValue = function(arr1, arr2, d) {
var total = 0;
for (var i = 0; i < arr1.length; i++) {
var ok = true;
for (var j = 0; j < arr2.length; j++) {
if (Math.abs(arr1[i] - arr2[j]) <= d) { ok = false; break; }
}
if (ok) total++;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search