1385. Find the Distance Value Between Two Arrays

  • Array
  • Two Pointers
  • Binary Search
  • Sorting
TIME
O((n + m) log m)
SPACE
O(m)
problem on leetcode ↗source on github ↗

Intuition

arr1[i] counts when no arr2 value lies within d of it, which means the range [x - d, x + d] holds no arr2 value. Once arr2 is sorted, one binary search answers that: find the smallest value >= x - d and check whether it is still <= x + d.

Approach

  1. Sort arr2.
  2. For each x in arr1, find the first index i with arr2[i] >= x - d.
  3. Count x if i is past the end or arr2[i] > x + d.

Complexity

  • Time: O((n + m) log m), where n = len(arr1) and m = len(arr2)
  • Space: O(1) beyond the sort (Python's sort uses O(m))

Edge Cases

  • d = 0: x fails only on an exact match
  • Every arr2 value is below x - d: the search runs off the end, and x counts
  • Every arr2 value is above x + d: the search lands on index 0, the check fails, and x counts
  • Duplicates in arr1 are counted separately, and duplicates in arr2 change nothing
  • A value exactly d away is within range, because the condition is <= d

Code

from bisect import bisect_left


class Solution:
    def findTheDistanceValue(self, arr1: list[int], arr2: list[int], d: int) -> int:
        """
        1385. Find the Distance Value Between Two Arrays
        Time: O((n + m) log m)
        Space: O(m)
        """
        arr2 = sorted(arr2)
        m = len(arr2)
        count = 0
        for x in arr1:
            # x counts when no arr2 value lies in [x - d, x + d].
            i = bisect_left(arr2, x - d)
            if i == m or arr2[i] > x + d:
                count += 1
        return count