Shrink the Squared Gaps

Medium

You are given two integer arrays left and right of the same length n. Their mismatch is the sum of (left[i] - right[i])² over every i. In one move you increase or decrease a single element by 1. You may make at most moves_left moves in left and at most moves_right moves in right. Elements are allowed to go negative. Return the smallest mismatch you can reach.

Example 1

left=[3, 8, 1], right=[6, 2, 1], moves_left=2, moves_right=1 → 18

The gaps are 3, 6 and 0. All three moves are best spent on the largest gap: 6 → 3. The result is 3² + 3² + 0² = 18.

Example 2

left=[10, 20], right=[0, 0], moves_left=0, moves_right=0 → 500

No moves at all: 10² + 20² = 500.

Example 3

left=[4, 4], right=[1, 7], moves_left=10, moves_right=0 → 0

Both gaps are 3, so 6 moves erase them and there are 10 available. The answer is 0.

Constraints

1 ≤ n ≤ 10⁵
len(left) = len(right) = n
0 ≤ left[i], right[i] ≤ 10⁵
0 ≤ moves_left, moves_right ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Sorting Heap (Priority Queue)

Similar problems

Prices That Fade With Each Sale Medium Studios for Recording Sessions Medium K-th Smallest in a Sorted Grid Medium Stick Triples That Form a Triangle Medium Jobs With a Cooldown Medium

Input

left=[3, 8, 1], right=[6, 2, 1], moves_left=2, moves_right=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 119 tests on the server, hidden ones included.