Find the Distance Value Between Two Arrays
EasyPrompt
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=2Example 2:
Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2Example 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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward solution is to use nested loops to check every pair of elements, one from arr1 and one from arr2. For each element in arr1, we iterate through all elements of arr2 to see if any pair has an absolute difference less than or equal to d. If no such element is found in arr2 for the current element of arr1, we increment our distance counter.
Algorithm
- Initialize a counter
distanceto 0. - For each element
num1inarr1:- Assume
num1satisfies the condition by setting a flagis_validtotrue. - For each element
num2inarr2:- If the absolute difference
|num1 - num2|is less than or equal tod, thennum1does not satisfy the distance condition. - Set
is_validtofalseand break the inner loop since we've found a 'close' element.
- If the absolute difference
- If
is_validis stilltrueafter checking all elements inarr2, it means no close element was found. Incrementdistance.
- Assume
- After iterating through all elements of
arr1, returndistance.
Walkthrough
This approach directly translates the problem statement into code. We iterate through arr1 with an outer loop and arr2 with an inner loop. A flag is used for each element of arr1 to track if a 'close' element from arr2 has been found. If the inner loop completes without finding any close element, we increment the final count.
Here is the algorithm:
- Initialize a counter
distanceto 0. - For each element
num1inarr1:- Assume
num1satisfies the condition by setting a flagis_validtotrue. - For each element
num2inarr2:- If the absolute difference
|num1 - num2|is less than or equal tod, thennum1does not satisfy the distance condition. - Set
is_validtofalseand break the inner loop since we've found a 'close' element.
- If the absolute difference
- If
is_validis stilltrueafter checking all elements inarr2, it means no close element was found. Incrementdistance.
- Assume
- After iterating through all elements of
arr1, returndistance.
class Solution { public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { int distanceValue = 0; for (int num1 : arr1) { boolean foundCloseElement = false; for (int num2 : arr2) { if (Math.abs(num1 - num2) <= d) { foundCloseElement = true; break; } } if (!foundCloseElement) { distanceValue++; } } return distanceValue; }}Complexity
Time
O(n * m), where `n` is the length of `arr1` and `m` is the length of `arr2`. This is because for each of the `n` elements in `arr1`, we iterate through all `m` elements of `arr2`.
Space
O(1) extra space, as we only use a few variables to store the count and a boolean flag.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, making it very memory efficient.
Cons
Highly inefficient for large arrays, with a quadratic time complexity.
Likely to result in a 'Time Limit Exceeded' error on platforms with stricter time limits for larger inputs.
A more optimized approach involves sorting both arrays first. By using two pointers, one for each array, we can check the distance condition in a single pass through both arrays. As we iterate through the sorted arr1, we only need to advance our pointer in the sorted arr2, avoiding repeated scans.
Algorithm
- Sort both
arr1andarr2in non-decreasing order. - Initialize two pointers,
iforarr1andjforarr2, both to 0. - Initialize a counter
distanceValueto 0. - Iterate with pointer
ifrom0toarr1.length - 1:- Advance pointer
jas long asj < arr2.lengthandarr2[j] < arr1[i] - d. This skips elements inarr2that are too small for the currentarr1[i]. - Check if a close element exists. A close element does not exist if
jhas reached the end ofarr2ORarr2[j]is already too large (i.e.,arr2[j] > arr1[i] + d). - If no close element is found, increment
distanceValue.
- Advance pointer
- Return
distanceValue.
Walkthrough
The key idea is that once both arrays are sorted, for an element arr1[i], we don't need to check all of arr2. We only need to look at a 'window' of arr2. As i increases, arr1[i] increases, and this window in arr2 also slides forward. This monotonicity allows us to use a second pointer j for arr2 that only moves forward, leading to a linear time scan after the initial sort.
Here is the algorithm:
- Sort both
arr1andarr2in non-decreasing order. - Initialize two pointers,
iforarr1andjforarr2, both to 0. - Initialize a counter
distanceValueto 0. - Iterate with pointer
ifrom0toarr1.length - 1:- Advance pointer
jas long asj < arr2.lengthandarr2[j] < arr1[i] - d. This skips elements inarr2that are too small for the currentarr1[i]. - Check if a close element exists. A close element does not exist if
jhas reached the end ofarr2ORarr2[j]is already too large (i.e.,arr2[j] > arr1[i] + d). - If no close element is found, increment
distanceValue.
- Advance pointer
- Return
distanceValue.
import java.util.Arrays; class Solution { public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { Arrays.sort(arr1); Arrays.sort(arr2); int i = 0, j = 0; int distanceValue = 0; while (i < arr1.length) { // Advance j while arr2[j] is too small for arr1[i] while (j < arr2.length && arr2[j] < arr1[i] - d) { j++; } // Check if arr2 is exhausted or if arr2[j] is too large if (j == arr2.length || arr2[j] > arr1[i] + d) { distanceValue++; } else { // arr2[j] is in the range [arr1[i]-d, arr1[i]+d], so arr1[i] is not valid. // We still need to check the next arr1 element, but what if it's the same as current? // The problem is that one arr2[j] can invalidate multiple arr1[i]s. // A better way is to iterate through arr1 and check against arr2. } i++; } // The above logic is tricky. A clearer two-pointer logic is: i = 0; j = 0; int count = 0; while(i < arr1.length && j < arr2.length){ if(arr1[i] - arr2[j] > d){ j++; } else if (arr2[j] - arr1[i] > d){ count++; i++; } else { i++; } } count += arr1.length - i; return count; }}Complexity
Time
O(n log n + m log m), dominated by the time to sort both arrays. The subsequent two-pointer scan takes O(n + m) time.
Space
O(log n + log m) or O(1), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives takes O(log n) stack space.
Trade-offs
Pros
Much more efficient than brute force for large arrays.
The main logic after sorting is a single linear scan, which is very fast.
Cons
Requires sorting both arrays, which might not be ideal if the arrays are very large.
The
O(n log n)term from sortingarr1can make this approach slower than the binary search method ifnis large.
This approach improves upon the brute-force method by optimizing the search within arr2. Instead of a linear scan, we can sort arr2 first. Then, for each element in arr1, we use binary search on arr2 to quickly determine if there's any element within the distance d. This avoids both the quadratic complexity of the brute-force method and the need to sort arr1 as required by the two-pointer approach.
Algorithm
- Sort the array
arr2in non-decreasing order. - Initialize a counter
distanceValueto 0. - For each element
num1inarr1:- Define the search range
[num1 - d, num1 + d]. - Perform a binary search on the sorted
arr2to check if any element falls within this range. - To do this, search for an element
num2wherenum1 - d <= num2 <= num1 + d. - If the binary search does not find any such element, increment
distanceValue.
- Define the search range
- Return
distanceValue.
Walkthrough
The core idea is to replace the O(m) linear scan of the inner loop with an O(log m) binary search. This is possible if arr2 is sorted. For each num1 from arr1, we are looking for any num2 in arr2 such that |num1 - num2| <= d, which is equivalent to checking if arr2 contains any element in the closed interval [num1 - d, num1 + d].
Here is the algorithm:
- Sort the array
arr2in non-decreasing order. - Initialize a counter
distanceValueto 0. - For each element
num1inarr1:- Define the search range
[num1 - d, num1 + d]. - Perform a binary search on the sorted
arr2to check if any element falls within this range. - If the binary search does not find any such element, increment
distanceValue.
- Define the search range
- Return
distanceValue.
import java.util.Arrays; class Solution { public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { Arrays.sort(arr2); int distanceValue = 0; for (int num1 : arr1) { if (!hasCloseElement(arr2, num1, d)) { distanceValue++; } } return distanceValue; } private boolean hasCloseElement(int[] arr, int value, int d) { int left = 0; int right = arr.length - 1; int lowerBound = value - d; int upperBound = value + d; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= lowerBound && arr[mid] <= upperBound) { return true; // Found an element within the range } else if (arr[mid] < lowerBound) { left = mid + 1; } else { // arr[mid] > upperBound right = mid - 1; } } return false; // No element found in the range }}Complexity
Time
O(m log m + n log m). It takes O(m log m) to sort `arr2`. Then, for each of the `n` elements in `arr1`, we perform a binary search on `arr2`, which takes O(log m) time.
Space
O(log m) or O(1), depending on the space used by the sorting algorithm for `arr2`.
Trade-offs
Pros
Generally the most efficient and consistent approach.
Avoids sorting
arr1, which makes it faster than the two-pointer approach whennis large.
Cons
Implementation of binary search for a range can be slightly more complex than a simple value search.
Solutions
Solution
class Solution {public int findTheDistanceValue(int[] arr1, int[] arr2, int d) { Arrays.sort(arr2); int ans = 0; for (int a : arr1) { if (check(arr2, a, d)) { ++ans; } } return ans; }private boolean check(int[] arr, int a, int d) { int l = 0, r = arr.length; while (l < r) { int mid = (l + r) >> 1; if (arr[mid] >= a - d) { r = mid; } else { l = mid + 1; } } return l >= arr.length || arr[l] > a + d; }}class Solution {public: int findTheDistanceValue(vector<int> &arr1, vector<int> &arr2, int d) { auto check = [&](int a) -> bool { auto it = lower_bound(arr2.begin(), arr2.end(), a - d); return it == arr2.end() || *it > a + d; }; sort(arr2.begin(), arr2.end()); int ans = 0; for (int &a : arr1) { ans += check(a); } return ans; }};class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: def check(a: int) -> bool: i = bisect_left(arr2, a - d) return i == len(arr2) or arr2[i] > a + d arr2 . sort() return sum(check(a) for a in arr1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.