Leetcode 1946 Solution

This article provides solution to leetcode question 1946 (minimum-absolute-sum-difference)
Categories:
Tags:
Access this page by simply typing in "lcs 1946" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-absolute-sum-difference

Solution

class Solution:
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
        d = list(zip(nums1, nums2))
        d.sort()



        s = 0
        for num1, num2 in d:
            s = (s + abs(num1 - num2)) % 1000000007



        min_diff = 0
        for i in range(len(d)):
            target = d[i][1]



            l = 0
            r = len(d) - 1
            while l < r:
                m = (l + r) // 2



                if d[m][0] >= target:
                    r = m
                else:
                    l = m + 1



            if l == 0 or l == len(d) - 1 and d[l][0] < d[i][1]:
                min_diff = min(min_diff, abs(d[l][0] - d[i][1]) - abs(d[i][0] - d[i][1]))
            else:
                min_diff = min(
                    min_diff,
                    abs(d[l][0] - d[i][1]) - abs(d[i][0] - d[i][1]),
                    abs(d[l - 1][0] - d[i][1]) - abs(d[i][0] - d[i][1]),
                )



        return (s + min_diff) % 1000000007