Problem statement

https://leetcode.com/problems/minimum-moves-to-make-array-complementary/

Solution

The idea for each pair of complementary numbers, imagine 3, 4 and limit = 6. Then we can get numbers from 2 to 12, and we need the following number of moves:

[inf, inf, 2, 2, 1, 1, 1, 0, 1, 1, 1, 2, 2]

So, to get 7 we need zero moves, because 3 + 4 already equal to 7. To get 4, 5, 6 we can make 1 move: for example to get 4 we can make it as 3 + 1, and so on. Also we can get numbers 8, 9, 10, using 1 move. In general, to make 1 move, we can get numbers from min(a,b) + 1 to max(a,b) + limit.

Now, we need to get this array for all pairs of complementary numbers and sum all of them and find element with smallest value. There is a trick, how we can do it efficiently: first of all, let us invert array, that is consider

[inf, inf, 0, 0, 1, 1, 1, 2, 1, 1, 1, 0, 0].

And then we use cumulative sums trick, if we add two following arrays, than cumulative sum will be exactly what we need.

[inf, inf, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1, 0]

[inf, inf, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0]

So, we just do what we discussed, and get the solution.

Complexity

Time complexity O(n + k), where k is our limit and n is length of nums. Space complexity is O(k).

Code

class Solution:
    def minMoves(self, nums, k):
        n = len(nums)//2
        diffs = [0]*(2*k+2)
        for i in range(n):
            a, b = nums[i], nums[-1-i]
            diffs[min(a,b) + 1] += 1
            diffs[max(a,b) + k+1] -= 1
            diffs[a+b] += 1
            diffs[a+b+1] -= 1

        return 2*n - max(accumulate(diffs))

Remark

See similar Problem 0798 Smallest Rotation with Highest Score.