Minimum Sum of Squared Difference LeetCode solution in Python

1
# Runtime: 1506 ms (Top 29.6%) | Memory: 34.22 MB (Top 74.0%)
2

3

4
class Solution:
5
    def minSumSquareDiff(
6
        self, nums1: List[int], nums2: List[int], k1: int, k2: int
7
    ) -> int:
8
        n = len(nums1)
9
        k = k1 + k2  # can combine k's because items can be turned negative
10
        diffs = sorted((abs(x - y) for x, y in zip(nums1, nums2)))
11

12
        # First binary search to find our new max for our diffs array
13
        l, r = 0, max(diffs)
14
        while l < r:
15
            mid = (l + r) // 2
16

17
            # steps needed to reduce all nums greater than newMax
18
            steps = sum(max(0, num - mid) for num in diffs)
19

20
            if steps <= k:
21
                r = mid
22
            else:
23
                l = mid + 1
24

25
        newMax = l
26
        k -= sum(max(0, num - newMax) for num in diffs)  # remove used k
27

28
        # Second binary search to find first index to replace with max val
29
        l, r = 0, n - 1
30
        while l < r:
31
            mid = (l + r) // 2
32
            if diffs[mid] < newMax:
33
                l = mid + 1
34
            else:
35
                r = mid
36

37
        # Replace items at index >= l with newMax
38
        diffs = diffs[:l] + [newMax] * (n - l)
39

40
        # Use remaining steps to reduce overall score
41
        for i in range(len(diffs) - 1, -1, -1):
42
            if k == 0 or diffs[i] == 0:
43
                break
44
            diffs[i] -= 1
45
            k -= 1
46

47
        return sum(diff * diff for diff in diffs)