Find the Distance Value Between Two Arrays

Difficulty: Easy | Acceptance: 71.70% | Paid: No Topics: Array, Two Pointers, Binary Search, Sorting

Given two integer arrays arr1 and arr2 and an 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.

• Examples
• Constraints
• Brute Force
• Sorting + Binary Search
• Sorting + Two Pointers

Examples

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

Brute Force

Intuition Check every element in arr1 against every element in arr2 to see if the distance condition is violated.

Steps

• Initialize a count variable to 0.
• Iterate through each element x in arr1.
• For each x, iterate through each element y in arr2.
• If |x - y| <= d, mark x as invalid and break the inner loop.
• If the inner loop completes without finding a valid y, increment the count.
• Return the count.

class Solution:
    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
        count = 0
        for x in arr1:
            valid = True
            for y in arr2:
                if abs(x - y) <= d:
                    valid = False
                    break
            if valid:
                count += 1
        return count

Complexity

• Time: O(n * m) where n is the length of arr1 and m is the length of arr2.
• Space: O(1)
• Notes: Simple to implement but inefficient for large arrays.

Sorting + Binary Search

Intuition Sort arr2. For each element in arr1, use binary search to find the closest elements in arr2. If the closest element is still farther than d, the element is valid.

Steps

• Sort arr2.
• Initialize count to 0.
• For each x in arr1:
  • Use binary search to find the index where x would be inserted in arr2.
  • Check the element at the found index (if it exists) and the element at index - 1 (if it exists).
  • If both valid neighbors satisfy |x - neighbor| > d, increment count.
• Return count.

import bisect

class Solution:
    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
        arr2.sort()
        count = 0
        for x in arr1:
            idx = bisect.bisect_left(arr2, x)
            valid = True
            if idx < len(arr2) and abs(arr2[idx] - x) <= d:
                valid = False
            if idx > 0 and abs(arr2[idx - 1] - x) <= d:
                valid = False
            if valid:
                count += 1
        return count

Complexity

• Time: O(m log m + n log m) where m is the length of arr2 and n is the length of arr1.
• Space: O(1) or O(m) depending on the sorting algorithm.
• Notes: More efficient than brute force, especially when arr2 is large.

Sorting + Two Pointers

Intuition Sort both arrays. Use two pointers to traverse arr1 and arr2 simultaneously to check for valid elements.

Steps

• Sort arr1 and arr2.
• Initialize count to 0 and pointer j to 0.
• Iterate through each x in arr1:
  • Move j forward while arr2[j] < x - d (arr2[j] is too small to be within distance d).
  • Check if arr2[j] is within distance d (i.e., arr2[j] <= x + d).
  • If arr2[j] is not within distance d (meaning it’s > x + d or we ran out of elements), increment count.
• Return count.

class Solution:
    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
        arr1.sort()
        arr2.sort()
        count = 0
        j = 0
        m = len(arr2)
        for x in arr1:
            while j < m and arr2[j] < x - d:
                j += 1
            if j == m or arr2[j] > x + d:
                count += 1
        return count

Complexity

• Time: O(n log n + m log m) due to sorting.
• Space: O(1) or O(n + m) depending on sorting.
• Notes: Efficient and avoids the overhead of binary search for each element.