2333. Minimum Sum of Squared Difference

Array Binary Search Greedy Sorting Heap (Priority Queue)

Time: O(n + maxDiff)

Space: O(maxDiff)

Problem Overview

Only the absolute difference at each index matters, and a change to either array moves that difference by one, so k1 and k2 merge into a single budget k.

Intuition

Only the absolute difference at each index matters, and a change to either array moves that difference by one, so k1 and k2 merge into a single budget k. Squares grow fastest at the top, so every unit should lower the current largest difference. Spending units that way flattens the largest values together. Since differences are bounded, counting them in buckets and sweeping levels from the top finds the final shape directly, without a heap.

Algorithm

1Compute every difference, its total, and the largest one. If the total is at most k, every difference can reach 0, so return 0.
2Count how many indexes have each difference value.
3Sweep levels from the largest down. The group is every index at or above the current level. Lowering the whole group by one level costs its size.
4Stop at the first level where k is smaller than the group. There, k of the group drop one more level and the rest stay.
5Add the squares for that group and for every smaller bucket, using long arithmetic.

Example Walkthrough

Input: nums1 = [1,4,10,12], nums2 = [5,8,6,9], k1 = 1, k2 = 1

1.The differences are 4, 4, 4, and 3, and the budget is 2.
2.Three indexes share the top level 4, so the group cannot drop as a whole. Two of them go down to 3.
3.The values become 3, 3, 4, and 3, so the sum of squares is 9 + 9 + 16 + 9.

Output: 43

Common Pitfalls

•Add k1 and k2 as long values. Each can be up to a billion, so their sum overflows an int.
•Return 0 early when the budget covers every difference, or the sweep runs past level 0.
•Squares can reach about 10 to the power 10 each, so the answer needs a long.
•A max heap that lowers one level per step is also correct, but the bucket sweep avoids the log factor and the allocations.

2333.cs

// Approach: Only |nums1[i] - nums2[i]| matters, and k1 and k2 are
// interchangeable, so there is one budget k. Each unit should lower the
// largest difference. Count differences in buckets, then sweep levels from
// the top: all differences at or above a level act as one group of size c,
// and lowering the group by one level costs c. Stop at the first level where
// k < c. At that level k of the group drop one more level and the rest stay.
// Smaller buckets keep their values.
// Time: O(n + maxDiff) Space: O(maxDiff)

public class Solution
{
    public long MinSumSquareDiff(int[] nums1, int[] nums2, int k1, int k2)
    {
        int n = nums1.Length;
        int maxDiff = 0;
        long total = 0;
        for (int i = 0; i < n; i++)
        {
            int d = Math.Abs(nums1[i] - nums2[i]);
            total += d;
            if (d > maxDiff)
                maxDiff = d;
        }

        long k = (long)k1 + k2;
        if (total <= k)
            return 0;

        int[] count = new int[maxDiff + 1];
        for (int i = 0; i < n; i++)
            count[Math.Abs(nums1[i] - nums2[i])]++;

        long group = 0;
        int level = maxDiff;
        for (; level > 0; level--)
        {
            group += count[level];
            if (k < group)
                break;
            k -= group;
        }

        long lower = level - 1;
        long ans = (group - k) * level * level + k * lower * lower;
        for (int v = level - 1; v > 0; v--)
            ans += (long)count[v] * v * v;
        return ans;
    }
}

Was this solution helpful?