IRAMIACADEMY Picture it. Then code it.
Problem 2333Medium

Minimum Sum of Squared Difference

Array · Binary Search · Greedy · Sorting

Level-by-level flattening with gap counts

solution.py
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))
Time O(n + M)Space O(n + M)

The code from the episode, ready for LeetCode's Python 3 editor: paste it in and submit.

The idea

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.

Check our socials
Another way: Shrink the biggest gap, one move at a time
solution.py
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)
Time O(n) if k ≥ S, else O(n · (k + 1))Space O(n)