Domain 1EasyCORE

Find the Distance Value Between Two Arrays

The problem requires us to find the distance value between two integer arrays `arr1` and `arr2`. The distance value is defined as the number of elements in `arr1` such that there is no element in `arr2` where the absolute difference between the elements is less than or equal to a given integer `d`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1385. Find the Distance Value Between Two Arrays

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 66.4%


Problem Breakdown

The problem requires us to find the distance value between two integer arrays arr1 and arr2. The distance value is defined as the number of elements in arr1 such that there is no element in arr2 where the absolute difference between the elements is less than or equal to a given integer d.

Inputs:

  • Two integer arrays, arr1 and arr2.
  • An integer d.

Output:

  • An integer representing the distance value.

Implicit Constraints/Edge Cases:

  • Arrays can be empty.
  • Elements in the arrays can be negative or positive.
  • The value of d can be zero, which means no element in arr1 should have any element in arr2 with an absolute difference of zero.

Intuition

A brute-force approach would involve checking each element in arr1 against every element in arr2 to see if the absolute difference is less than or equal to d. This approach has a time complexity of O(n * m), where n is the length of arr1 and m is the length of arr2.

A better approach involves sorting arr2 and using binary search for each element in arr1. By sorting, we can efficiently determine if there exists an element in arr2 within the range [arr1[i] - d, arr1[i] + d] using binary search. This reduces the time complexity to O(n log m).

Approach

  1. Sort the array arr2.
  2. For each element in arr1, use binary search to check if there exists an element in arr2 within the range [arr1[i] - d, arr1[i] + d].
  3. If no such element is found for a particular element in arr1, increment the distance value.
  4. Return the distance value.

Complexity Analysis

  • Time Complexity: O(n log m), where n is the length of arr1 and m is the length of arr2. Sorting arr2 takes O(m log m) time, and for each element in arr1, we perform a binary search which takes O(log m) time.
  • Space Complexity: O(1), as we are using only a constant amount of extra space.

Solution

def findTheDistanceValue(arr1, arr2, d):
    arr2.sort()
    distance_value = 0
    
    for num in arr1:
        left, right = 0, len(arr2) - 1
        found = False
        
        while left <= right:
            mid = (left + right) // 2
            if abs(num - arr2[mid]) <= d:
                found = True
                break
            elif arr2[mid] < num - d:
                left = mid + 1
            else:
                right = mid - 1
        
        if not found:
            distance_value += 1
    
    return distance_value

Edge Cases Handled

  • Empty Arrays: If either arr1 or arr2 is empty, the function will handle it gracefully. If both are empty, the distance value will be zero.
  • Negative Numbers: The solution correctly handles negative numbers in both arrays.
  • Zero Distance (d = 0): The binary search ensures that if d is zero, no element in arr1 should have an exact match in arr2.
  • Large Arrays: The solution efficiently handles large arrays due to the use of sorting and binary search.