Problem statement

https://binarysearch.com/problems/Minimum-Difference/

Solution

Similar to Leetcode 1385. Find the Distance Value Between Two Arrays. What we need to do here is to sort on array and use binary search of all elements in sorted array. Or we can sort both of them and use two poitners techinique.

Complexity

It is O(n log n + m log n) for time and O(log n) for space.

Code

from bisect import bisect

class Solution:
    def solve(self, arr1, arr2):
        arr2.sort()
        cnt, ans = 0, float("inf")
        for x in arr1:
            i = bisect(arr2, x)
            if i < len(arr2): ans = min(ans, arr2[i] - x)
            if i > 0: ans = min(ans, x - arr2[i-1])
        return ans