1385. Find the Distance Value Between Two Arrays LeetCode Solution

In this guide, you will get 1385. Find the Distance Value Between Two Arrays LeetCode Solution with the best time and space complexity. The solution to Find the Distance Value Between Two Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Find the Distance Value Between Two Arrays solution in C++
  4. Find the Distance Value Between Two Arrays solution in Java
  5. Find the Distance Value Between Two Arrays solution in Python
  6. Additional Resources
1385. Find the Distance Value Between Two Arrays LeetCode Solution image

Problem Statement of Find the Distance Value Between Two Arrays

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-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

See also  204. Count Primes LeetCode Solution

Complexity Analysis

  • Time Complexity: O(\max(|\texttt{arr1}|, |\texttt{arr2}|)\log |\texttt{arr2}|)
  • Space Complexity: O(1)

1385. Find the Distance Value Between Two Arrays LeetCode Solution in C++

class Solution {
 public:
  int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
    int ans = 0;

    ranges::sort(arr2);

    for (const int a : arr1) {
      const auto it = lower_bound(begin(arr2), end(arr2), a);
      if ((it == arr2.end() || *it - a > d) &&
          (it == arr2.begin() || a - *prev(it) > d))
        ++ans;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1385. Find the Distance Value Between Two Arrays LeetCode Solution in Java

class Solution {
  public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    int ans = 0;

    Arrays.sort(arr2);

    for (final int a : arr1) {
      int i = Arrays.binarySearch(arr2, a);
      i = i < 0 ? -i - 1 : i;
      if ((i == arr2.length || arr2[i] - a > d) && (i == 0 || a - arr2[i - 1] > d))
        ++ans;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1385. Find the Distance Value Between Two Arrays LeetCode Solution in Python

class Solution:
  def findTheDistanceValue(
      self,
      arr1: list[int],
      arr2: list[int],
      d: int,
  ) -> int:
    ans = 0

    arr2.sort()

    for a in arr1:
      i = bisect.bisect_left(arr2, a)
      if ((i == len(arr2) or arr2[i] - a > d) and
              (i == 0 or a - arr2[i - 1] > d)):
        ans += 1

    return ans
# code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.