Level-by-level flattening with gap counts
class Solution: def minSumSquareDiff(self, nums1, nums2, k1, k2): budget = k1 + k2 gaps = [abs(x - y) for x, y in zip(nums1, nums2)] count = [0] * (max(gaps) + 1) for gap in gaps: count[gap] += 1 for level in range(len(count) - 1, 0, -1): if budget >= count[level]: # lower the whole level budget -= count[level] count[level - 1] += count[level] count[level] = 0 else: # only some gaps drop one step count[level - 1] += budget count[level] -= budget break return sum(num * gap * gap for gap, num in enumerate(count))
The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.
Learn why every move should shrink the largest gap, and how counting gaps per height lets you lower a whole level at once instead of one step at a time. We trace both approaches on a real example and write the counting solution line by line.
class Solution: def minSumSquareDiff(self, nums1, nums2, k1, k2): # Only the gap |nums1[i] - nums2[i]| matters, and a move on either # array shrinks a gap by 1, so k1 and k2 form one shared budget. gaps = [abs(x - y) for x, y in zip(nums1, nums2)] budget = k1 + k2 # If we can close every gap, the answer is 0. if budget >= sum(gaps): return 0 # Greedy: each move goes to the currently largest gap, because # shrinking g to g-1 saves 2g - 1, which is biggest for the max gap. for _ in range(budget): biggest = max(range(len(gaps)), key=lambda i: gaps[i]) gaps[biggest] -= 1 return sum(gap * gap for gap in gaps)