1385. Find the Distance Value Between Two Arrays
Problem Description
The goal of this problem is to compare two lists of integers, arr1
and arr2
, and determine the number of elements in arr1
that are at least distance d
apart from every element in arr2
. We define this "distance value" as the count of such arr1[i]
elements for which no arr2[j]
exists where |arr1[i]-arr2[j]| <= d
. In other words, we're counting how many elements in arr1
are not within d
distance of any element in arr2
.
Intuition
The key to solving this problem efficiently is to recognize that we can exploit the properties of sorted arrays. By sorting arr2
, we can quickly determine if any given element in arr1
is within the distance d
to elements in arr2
using binary search, rather than comparing it to every element in arr2
.
The intuition behind the solution is to sort arr2
first. Then, for each element a
in arr1
, we perform a binary search to find the position where a - d
would fit in arr2
. This tells us the index of the first element in arr2
that could potentially be within distance d
of a
. We call the helper function check
with the current element a
to verify that indeed there is no arr2[j]
such that |a - arr2[j]| <= d
.
Since arr2
is sorted, if the element at the found index is greater than a + d
, then a
is not within distance d
of any element in arr2
. If the found index is equal to the length of arr2
, it means a - d
is larger than any element in arr2
, and thus also satisfies the condition.
Finally, we count and sum up all such a
from arr1
that satisfy the condition by using the sum
function on the generator expression that iterates through arr1
and applies the check
function to each element.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The solution leverages binary search and sorting to efficiently determine if any elements in arr1
are within d
distance of elements in arr2
.
Here is a step-by-step explanation of the algorithm:
-
Sorting
arr2
: The first step is to sort the arrayarr2
. Sorting is important because it enables us to use binary search, which significantly reduces the time complexity of searching withinarr2
fromO(n)
toO(log n)
for each element inarr1
. -
Defining a helper function
check
: Inside theSolution
class, a helper function namedcheck
is defined which takes an integera
as input. The purpose of this function is to determine if there is an element inarr2
withind
distance ofa
. -
Performing binary search with
bisect_left
: This function usesbisect_left
from Python'sbisect
module. Given a sorted array and a target value,bisect_left
returns the index where the target should be inserted to keep the array sorted. If we search fora - d
inarr2
, this will give us the lowest indexi
at whicha - d
could be inserted without violating the sorting order. This indexi
helps us quickly find the potential candidates inarr2
that could be withind
distance froma
. -
Checking the condition: The helper function then checks if the index
i
is at the end ofarr2
(meaning thata
is greater than all elements inarr2
plusd
), or if the element at indexi
inarr2
is greater thana + d
. If either of these conditions is true, it means that none of the elements inarr2
are withind
distance ofa
. In this case, the function returnsTrue
. -
Counting elements with the
sum
function: Finally, in thefindTheDistanceValue
method, the sum function iterates over each elementa
inarr1
and applies thecheck
function to it. This produces a generator ofTrue
orFalse
values, whereTrue
indicates thata
is at a valid distance from all elements inarr2
. The sum function then adds up all theTrue
values, which correspond to1
s, thus counting the elements inarr1
that satisfy the condition.
By utilizing a sorted array and binary search, the solution effectively reduces the number of comparisons that need to be made, resulting in an efficient algorithm with a lower time complexity suitable for large inputs.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us illustrate the solution approach with a small example:
Suppose we have arr1 = [1, 4, 5, 7]
, arr2 = [3, 6, 10]
, and d = 2
.
-
Sorting
arr2
: First, we sortarr2
, but it's already sorted in this case:arr2 = [3, 6, 10]
. -
Defining a helper function
check
: Thecheck
function will determine ifarr1[i]
is at least distanced
apart from every element inarr2
. -
Performing binary search with
bisect_left
:- For
a = 1
fromarr1
: We find the place where1 - 2
(which is-1
) would fit inarr2
usingbisect_left
. The index returned is0
because-1
is less than the first element inarr2
. Sincearr2[0]
is3
, and3
is greater than1 + 2
(3
is not within the distanced
from1
), the condition is satisfied. - For
a = 4
fromarr1
:bisect_left
of4 - 2
will return index1
because2
fits between3
and6
. However, the element at index1
is6
, which is not greater than4 + 2
; therefore, the condition is not satisfied, and4
is not at the required distance from an element inarr2
. - For
a = 5
fromarr1
: Using the same approach, the binary search returns index2
(for5 - 2
), andarr2[2]
is10
, which is greater than5 + 2
; hence,5
is at a valid distance from all elements inarr2
. - For
a = 7
fromarr1
: The binary search for7 - 2
returns index2
as well, and since10
is still greater than7 + 2
,7
also satisfies the condition.
- For
-
Checking the condition: As explained above, after performing the binary search, the helper function checks the conditions to confirm if
a
is at the required distance from all elements inarr2
. -
Counting elements with the
sum
function: We have found that elements1
,5
, and7
fromarr1
satisfy the condition of being at least distanced
from all elements ofarr2
. Hence, our distance value would be the count of these elements, which is3
.
Following the approach above, the findTheDistanceValue
method would return 3
for the given example, as there are three elements in arr1
that are at least distance d
away from every element in arr2
.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
6 # Helper function to check if there's an element in arr2 within
7 # the distance d of the element 'element_from_arr1'.
8 def is_valid(element_from_arr1: int) -> bool:
9 # Find the position in arr2 where 'element_from_arr1' - d could be inserted
10 # to maintain the sorted order.
11 index = bisect_left(arr2, element_from_arr1 - d)
12 # Return True if either:
13 # - index is at the end of arr2 (no element within distance d), or
14 # - the element at the found index is greater than 'element_from_arr1' + d
15 return index == len(arr2) or arr2[index] > element_from_arr1 + d
16
17 # Sort the second array to leverage binary searching.
18 arr2.sort()
19
20 # Use list comprehension to iterate over arr1, applying 'is_valid'
21 # function to each element, and sum the results. The result will be
22 # the count of elements in arr1 that satisfy the distance value condition.
23 return sum(is_valid(element) for element in arr1)
24
1class Solution {
2
3 // This function finds the distance value between two arrays.
4 public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
5 // Sort the second array to perform binary search later.
6 Arrays.sort(arr2);
7
8 // Initialize answer to count the number of elements meeting the condition.
9 int answer = 0;
10
11 // Loop over each element in the first array.
12 for (int elemArr1 : arr1) {
13 // Check if the element in the first array meets the distance condition.
14 if (isDistanceMoreThanD(arr2, elemArr1, d)) {
15 // Increment the answer if the condition is met.
16 answer++;
17 }
18 }
19 // Return the number of elements that meet the condition.
20 return answer;
21 }
22
23 // Helper function to check if the distance between an element and all elements in another array is more than d.
24 private boolean isDistanceMoreThanD(int[] sortedArr2, int elemArr1, int d) {
25 int left = 0;
26 int right = sortedArr2.length;
27
28 // Perform a binary search to find if there exists an element in arr2 that is within distance d of elemArr1.
29 while (left < right) {
30 int mid = left + (right - left) / 2; // Avoid potential overflow compared to (left + right) / 2.
31 if (sortedArr2[mid] >= elemArr1 - d) {
32 // If the middle element is within the lower bound of the distance, narrow the search to the left part.
33 right = mid;
34 } else {
35 // Otherwise, narrow the search to the right part.
36 left = mid + 1;
37 }
38 }
39
40 // After the binary search, if the left index is out of bounds, it means all elements in arr2 are less than elemArr1 - d.
41 // If the left index points to an element, that element must be greater than elemArr1 + d to satisfy the condition.
42 return left >= sortedArr2.length || sortedArr2[left] > elemArr1 + d;
43 }
44}
45
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to calculate the distance value between two arrays
7 int findTheDistanceValue(std::vector<int>& arr1, std::vector<int>& arr2, int d) {
8 // Lambda function to check if no element in arr2 lies within the range [a - d, a + d]
9 // If true, a contributes to the distance value
10 auto isDistanceValid = [&](int a) -> bool {
11 // Finding the first element in arr2 which is not less than a - d
12 auto it = std::lower_bound(arr2.begin(), arr2.end(), a - d);
13 // Check if the iterator reached the end (no such element) or the found element is greater than a + d
14 return it == arr2.end() || *it > a + d;
15 };
16
17 // Sort array arr2 to use binary search (required by std::lower_bound)
18 std::sort(arr2.begin(), arr2.end());
19
20 // Initialize the distance value answer
21 int ans = 0;
22
23 // Iterate over each element in arr1
24 for (int a : arr1) {
25 // Increment the distance value answer if the element a satisfies the isDistanceValid condition
26 ans += isDistanceValid(a);
27 }
28
29 // Return the computed distance value
30 return ans;
31 }
32};
33
1function findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
2 // Helper function that checks if any element in arr2 is within d distance of element 'value'
3 const isElementDistanceValid = (value: number): boolean => {
4 let left = 0;
5 let right = arr2.length;
6 while (left < right) {
7 // Find the middle index
8 const middle = Math.floor((left + right) / 2);
9 // Check if the middle element is within the allowed distance
10 if (arr2[middle] >= value - d) {
11 right = middle; // Element is too close, adjust the search range to the left
12 } else {
13 left = middle + 1; // Element is not close enough, adjust the search range to the right
14 }
15 }
16 // If left is equal to length of arr2 or the element at 'left' index is outside the distance 'd' from 'value', return true
17 return left === arr2.length || arr2[left] > value + d;
18 };
19
20 // Sort the second array to enable binary search
21 arr2.sort((a, b) => a - b);
22 // Initialize the count of elements that satisfy the condition
23 let validElementCount = 0;
24 // Iterate through the elements of arr1
25 for (const value of arr1) {
26 // Check if the current element satisfies the distance condition for every element in arr2
27 if (isElementDistanceValid(value)) {
28 // If condition is met, increment the count
29 validElementCount++;
30 }
31 }
32 // Return the final count of valid elements
33 return validElementCount;
34}
35
Time and Space Complexity
The given Python code defines a function findTheDistanceValue
that computes the distance value between two lists arr1
and arr2
, given a distance d
. Here's an analysis of the time and space complexity:
Time Complexity:
- Sorting
arr2
usingarr2.sort()
: The sort operation has a time complexity ofO(n log n)
wheren
is the length ofarr2
. - Iterating through
arr1
with the for loop: The loop runsm
times wherem
is the length ofarr1
. - The
check
function callsbisect_left
, a binary search function, for every elementa
inarr1
. The binary search runs inO(log n)
time. - Multiplying the above two factors, the for loop with the binary search operation results in a time complexity of
O(m log n)
.
Adding both parts, the overall time complexity of the code is dominated by the O(m log n)
part (since this part depends both on the length of arr1
and the fact that a binary search is performed on arr2
), assuming m log n
> n log n
, which might be the case if m
is significantly larger than n
or vice versa. Therefore, the total time complexity is O(m log n)
.
Space Complexity:
- The sorted version of
arr2
: Python'ssort()
function sorts the list in place, so it doesn't use any additional space other than a small constant amount, hence it has a space complexity ofO(1)
. - The check function itself and the binary search do not use extra space that scales with the input size (they use a constant amount of extra space).
Therefore, the space complexity of the entire function is O(1)
as there is no additional space used that depends on the input size of arr1
and arr2
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.