LeetCode 1385 - Find the Distance Value Between Two Arrays

The problem is asking us to compute the distance value between two arrays arr1 and arr2 given a threshold d. Specificall

leetcodeeasyarraytwo-pointersbinary-searchsorting

LeetCode Problem 1385

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem is asking us to compute the distance value between two arrays arr1 and arr2 given a threshold d. Specifically, the distance value is defined as the count of elements in arr1 for which no element in arr2 is within a distance of d, i.e., there is no arr2[j] such that the absolute difference |arr1[i] - arr2[j]| is less than or equal to d.

In simpler terms, for each element in arr1, we check if all elements in arr2 are "far enough" away according to the distance d. If they are, we increment our count.

The inputs are two integer arrays and a non-negative integer d. Constraints tell us the arrays are relatively small, with up to 500 elements, and element values range from -1000 to 1000. These bounds suggest that a solution with complexity up to $O(n \cdot m)$, where $n$ and $m$ are the sizes of the arrays, is acceptable, but a more efficient approach is possible.

Important edge cases include arrays where all elements overlap, arrays where one array is empty, elements exactly at the distance boundary d, and negative numbers.

Approaches

The brute-force approach is straightforward: for each element in arr1, check every element in arr2 and see if the absolute difference is less than or equal to d. If none of the elements in arr2 violate the distance condition, increment the count. This is guaranteed to be correct because it explicitly checks the definition, but it requires $O(n \cdot m)$ time.

The optimal approach leverages sorting and binary search. By sorting arr2, we can use binary search to efficiently find the closest element to arr1[i]. If the closest element is at a distance greater than d, then all other elements are also sufficiently far, allowing us to increment the count. Sorting arr2 takes $O(m \log m)$, and binary searching for each arr1[i] takes $O(n \log m)$, giving a faster solution than brute-force for larger inputs.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Check all pairs for distance
Optimal (Binary Search) O(m log m + n log m) O(1) Sort arr2, binary search closest element

Algorithm Walkthrough

  1. Sort the array arr2 in ascending order. This allows binary search operations to quickly locate the nearest element to any target.
  2. Initialize a counter distance_count to zero. This will track the number of elements in arr1 that satisfy the distance condition.
  3. For each element num in arr1, perform a binary search in arr2 to find the index of the smallest element that is greater than or equal to num. This index points to a candidate closest element.
  4. Check the absolute difference between num and this candidate element. Also check the element immediately before the candidate (if it exists), since it could be closer. If both differences are greater than d, increment distance_count.
  5. Continue this process for all elements in arr1.
  6. Return distance_count.

Why it works: Sorting guarantees that binary search finds the nearest neighbor efficiently. By checking the closest element and its predecessor, we ensure we cover both potential nearest elements. The property that all elements to the right of the found index are larger, and all to the left are smaller, ensures correctness.

Python Solution

from bisect import bisect_left
from typing import List

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        distance_count = 0
        
        for num in arr1:
            index = bisect_left(arr2, num)
            left_diff = abs(num - arr2[index-1]) if index > 0 else float('inf')
            right_diff = abs(num - arr2[index]) if index < len(arr2) else float('inf')
            
            if left_diff > d and right_diff > d:
                distance_count += 1
                
        return distance_count

The code first sorts arr2 to prepare for binary search. For each num in arr1, we use bisect_left to find the index of the first element in arr2 that is not less than num. We compute differences with both the element at that index and the previous element. If both differences are greater than d, it satisfies the distance condition.

Go Solution

import (
    "sort"
    "math"
)

func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
    sort.Ints(arr2)
    distanceCount := 0
    
    for _, num := range arr1 {
        index := sort.Search(len(arr2), func(i int) bool {
            return arr2[i] >= num
        })
        
        leftDiff := math.MaxInt
        rightDiff := math.MaxInt
        
        if index > 0 {
            leftDiff = abs(num - arr2[index-1])
        }
        if index < len(arr2) {
            rightDiff = abs(num - arr2[index])
        }
        
        if leftDiff > d && rightDiff > d {
            distanceCount++
        }
    }
    
    return distanceCount
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

In Go, sort.Search is used to find the insertion point for binary search. Differences are computed similarly to Python. Go uses math.MaxInt as a stand-in for infinity.

Worked Examples

Example 1:

arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2

arr2 sorted: [1, 8, 9, 10]

arr1[i] bisect index left_diff right_diff Count?
4 1 3 4 Yes
5 1 4 3 Yes
8 1 7 0 No

Output: 2

Example 2:

arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3

arr2 sorted: [-4, -3, 6, 10, 20, 30]

Check each element similarly; only 4 and 3 fail, so output: 2

Example 3:

arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6

Sorted arr2: [-5, -3, -2, 7, 10]

Only 100 is sufficiently far from all elements, so output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(m log m + n log m) Sorting arr2 costs O(m log m), binary search per arr1 element costs O(n log m)
Space O(1) In-place sort and constant extra variables

The optimal solution is efficient for the problem constraints because binary search avoids checking all pairs.

Test Cases

# Provided examples
assert Solution().findTheDistanceValue([4,5,8], [10,9,1,8], 2) == 2  # Example 1
assert Solution().findTheDistanceValue([1,4,2,3], [-4,-3,6,10,20,30], 3) == 2  # Example 2
assert Solution().findTheDistanceValue([2,1,100,3], [-5,-2,10,-3,7], 6) == 1  # Example 3

# Edge values
assert Solution().findTheDistanceValue([], [1,2,3], 0) == 0  # arr1 empty
assert Solution().findTheDistanceValue([1,2,3], [], 0) == 3  # arr2 empty
assert Solution().findTheDistanceValue([0], [0], 0) == 0  # boundary equals
assert Solution().findTheDistanceValue([1000], [-1000], 100) == 1  # max/min values
Test Why
arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 Basic example from problem statement
arr1 = [], arr2 = [1,2,3], d = 0 arr1 empty edge case
arr1 = [1,2,3], arr2 = [], d = 0 arr2 empty edge case
arr1 = [0], arr2 = [0], d = 0 Distance exactly zero
arr1 = [1000], arr2 = [-1000], d = 100