MediumNo. 2333
Minimum Sum of Squared Difference — LeetCode 2333 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Binary Search, Sorting, Heap (Priority Queue)
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given two positive 0-indexed integer arrays nums1 and nums2, both of length n. The sum of squared difference of arrays nums1 and nums2 is defined as the sum of (nums1[i] - nums2[i])2 for each 0 <= i < n.
Example
- Input
- nums1 = [1,2,3,4], nums2 = [2,10,20,19], k1 = 0, k2 = 0
- Output
- 579
- Explanation
- The elements in nums1 and nums2 cannot be modified because k1 = 0 and k2 = 0.
Python solution
class Solution:
def minSumSquareDiff(
self, nums1: List[int], nums2: List[int], k1: int, k2: int
) -> int:
d = [abs(a - b) for a, b in zip(nums1, nums2)]
k = k1 + k2
if sum(d) <= k:
return 0
left, right = 0, max(d)
while left < right:
mid = (left + right) >> 1
if sum(max(v - mid, 0) for v in d) <= k:
right = mid
else:
left = mid + 1
for i, v in enumerate(d):
d[i] = min(left, v)
k -= max(0, v - left)
for i, v in enumerate(d):
if k == 0:
break
if v == left:
k -= 1
d[i] -= 1
return sum(v * v for v in d)Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2333. Minimum Sum of Squared Difference is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1648 | Sell Diminishing-Valued Colored Balls | Medium |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 1268 | Search Suggestions System | Medium |
| 1337 | The K Weakest Rows in a Matrix | Easy |
| 1851 | Minimum Interval to Include Each Query | Hard |
| 2054 | Two Best Non-Overlapping Events | Medium |
Frequently asked questions
- How hard is LeetCode 2333. Minimum Sum of Squared Difference?
LeetCode 2333. Minimum Sum of Squared Difference is rated Medium on LeetCode.
- What topics does LeetCode 2333. Minimum Sum of Squared Difference cover?
LeetCode 2333. Minimum Sum of Squared Difference is tagged Greedy, Array, Binary Search, Sorting and Heap (Priority Queue) on LeetCode.