1674. Minimum Moves to Make Array Complementary

Minimum Moves to Make Array Complementary

Problem Statement (link)

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

---

Examples

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).

nums[0] + nums[3] = 1 + 3 = 4
nums[1] + nums[2] = 2 + 2 = 4
nums[2] + nums[1] = 2 + 2 = 4
nums[3] + nums[0] = 3 + 1 = 4

Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

---

Constraints

• n == nums.length
• 2 <= n <= 10^5
• 1 <= nums[i] <= limit <= 10^5
• n is even.

---

Example Walkthrough

nums = [1, 2, 4, 3], limit = 5

---

Pair (x, y) = (2, 4)

a = min(x, y) = min(2, 4) = 2
b = max(x, y) = max(2, 4) = 4

What is the range of values that the sum of any pair could have?
any number n from nums array can be 1 <= n <= limit
so the sum of any pair can be 2 <= sum_of_any_pair <= 2 * limit

For the current pair (2, 4), we need to loop through all possible sums and find the sum with the minimum changes:

sum	action	changes
2	change x = 1, y = 1	2 changes
3	change y = 1 (but it’s possible also to set x = 1 and y = 2 ?! that’s not the min change any more for the sum of 3)	1 change
4	change y = 2	1 change
5	change y = 3	1 change
6	same	0 changes
7	change x = 3	1 change
8	change x = 4	1 change
9	change x = 4, y = 5	2 changes
10	change x = 5, y = 5	2 changes

---

Observations

notice how the sums splitted into ranges, and for any pair to have a value from that a specific range it should have 0, 1, 2 changes:

• If 2 <= sum <= a then 2 changes
• If a+1 <= sum <= x+y-1 then 1 change
• If sum == x+y then 0 changes
• If x+y+1 <= sum <= b+limit then 1 change (leave b as is, and move a little higher till limit)
• If b+limit+1 <= sum <= 2*limit then both entries must be changed (noway)

so:

range	changes
[2, 2]	2 changes
[3, 5]	1 change
[6, 6]	0 changes
[7, 9]	1 change
[10, 10]	2 changes

Difference array for pair (2, 4):

 0  1  2   3  4  5   6  7  8  9  10
[0, 0, 2, -1, 0, 0, -1, 1, 0, 0,  1]

---

Now let’s consider another pair (1, 3)

x = 1
y = 3
a = min(x, y) = 1
b = max(x, y) = 3

range	changes
[2, 1]	not possible
[2, 3]	1 change
[4, 4]	0 changes
[5, 8]	1 change
[9, 10]	2 changes

Total difference array (both pairs combined):

 0  1  2   3   4  5   6  7  8  9  10
[0, 0, 3, -1, -1, 1, -1, 1, 0, 1,  1]

Prefix sum of the difference array across all pairs:

[0, 0, 3, 2, 1, 2, 1, 2, 2, 3, 4]

the changes on all pairs are represented by the prefix sum array, the min changes is related to {4, 6}

---

Solution

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        n = len(nums)
 
        diff = [0] * (2*limit + 2)
        for i in range(n // 2):
            x, y = nums[i], nums[n-i-1]
            a, b = min(x, y), max(x, y)
 
            diff[2]         += 2
            diff[a+1]       -= 1
            diff[x+y]       -= 1
            diff[x+y+1]     += 1
            diff[b+limit+1] += 1
 
        answer = inf
        acc = 0
        for i in range(2, 2*limit + 1):
            acc += diff[i]
            if acc < answer:
                answer = acc
 
        return answer