unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1385: Find the Distance Value Between Two Arrays

link

For each element from arr1 try against all elements in arr2.

If arr1 has m elements and arr2 has n elements, time: \mathcal{O}(m \cdot n), space: \mathcal{O}(1).

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        count = 0
        for x in arr1:
            count += (1 if all( abs(x-y) > d for y in arr2 ) else 0)
        return count

Insight: For a number x in nums1, if the closest number in nums2 is y and |x-y| > d, then all other numbers in nums2 must also be more than d distance away from x.

If nums2 were sorted, we could use binary-search to find y in \mathcal{O}( \lg{n} ) time. Because, lo always points to where a number should have been inserted in sorted order. So, y should be at lo-1 or lo.

Time: \mathcal{O}( \max{ (m, n) } \cdot \lg{n} ). Space would be that of sorting.

class Solution:
    def find_closest(self, x, nums) -> int:
        lo, hi = 0, len(nums)-1
        while lo <= hi:
            mid = (lo+hi) // 2
            if x == nums[mid]:
                return x
            if x < nums[mid]:
                hi = mid-1
            else:
                lo = mid+1

        left  = nums[lo-1] if lo > 0         else float('-inf')
        right = nums[lo  ] if lo < len(nums) else float('inf')

        return left if x-left <= right-x else right


    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        count = 0
        for x in arr1:
            y = self.find_closest(x, arr2)
            count += (1 if abs(x-y) > d else 0)
        return count

tanvirdotzaman

,

Leave a comment