Minimum Absolute Sum Difference LeetCode solution in Python

1
# Runtime: 2682 ms (Top 14.06%) | Memory: 30 MB (Top 26.09%)
2
class Solution:
3
    def minAbsoluteSumDiff(self, nums1: List[int], nums2: List[int]) -> int:
4
        n = len(nums1)
5
        diff = []
6
        sum = 0
7
        for i in range(n):
8
            temp = abs(nums1[i] - nums2[i])
9
            diff.append(temp)
10
            sum += temp
11
        nums1.sort()
12
        best_diff = []
13
        for i in range(n):
14
            idx = bisect.bisect_left(nums1, nums2[i])
15
            if idx != 0 and idx != n:
16
                best_diff.append(
17
                    min(abs(nums2[i] - nums1[idx]), abs(nums2[i] - nums1[idx - 1]))
18
                )
19
            elif idx == 0:
20
                best_diff.append(abs(nums2[i] - nums1[idx]))
21
            else:
22
                best_diff.append(abs(nums2[i] - nums1[idx - 1]))
23
        saved = 0
24
        for i in range(n):
25
            saved = max(saved, diff[i] - best_diff[i])
26
        return (sum - saved) % ((10**9) + (7))