1674

1674. Minimum Moves to Make Array Complementary (Medium)

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.

 

Example 1:

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.

Example 2:

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.

Example 3:

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

 

Constraints:

• n == nums.length
• 2 <= n <= 105
• 1 <= nums[i] <= limit <= 105
• n is even.

Related Topics:
Greedy

Solution 1. Difference Array

Assume we want to make all the pairs to sum to T, and (A, B) is a pair of numbers. We have the following cases:

1. 2 <= T <= min(A, B). We need 2 operations because we need to make both smaller.
2. min(A, B) < T < A + B. We need 1 operation because we only need to make the greater one smaller.
3. T == A + B. We need 0 operation.
4. A + B < T <= max(A, B) + limit. We need 1 operation because we only need to make the smaller one greater.
5. max(A, B) + limit < T <= 2 * limit. We need 2 operations because we need to make both greater.

We can calculate the boundary for each pair (A, B) and note down the corresponding operation needed in cnt array where cnt[i] means that we need cnt[i] operations when T == i.

We need to use the above 5 cases to add values into cnt.

For each pair (A, B), we do the following:

1. cnt[i] += 2 if 2 <= i <= min(A, B)
2. cnt[i] += 1 if min(A, B) < i < A + B
3. cnt[i] += 0 if i == A + B
4. cnt[i] += 1 if A + B < i <= max(A, B) + limit
5. cnt[i] += 2 if max(A, B) + limit < T <= 2 * limit

But for each pair we need to visit 2 * limit - 2 elements in cnt, and there are N / 2 pairs, so the time complexity is O(NL) which will get TLE.

To resolve this, we can make it a difference array, i.e. only save the difference of operations when we move from i - 1 to i.

Assume the difference array is delta, where delta[i] = cnt[i] - cnt[i - 1], i.e. the difference of operations needed when changing T from i - 1 to i.

For example, delta[3] = 1 means that if we change T from 2 to 3, we need one more operation.

So in this way, we don't need to change all 2 * limit - 2 elements. Instead, just change 5 break points:

1. delta[2] += 2.
2. delta[min(A, B) + 1] -= 1.
3. delta[A + B] -= 1.
4. delta[A + B + 1] += 1.
5. delta[max(A, B) + limit + 1] += 1.

And in the end we just need to go over the 2 * limit - 2 elements to get the operations needed for each T, and return the minimum among them.

Time complexity

Calculating the delta array takes O(N) time. Reconstructing the cnts from delta takes O(L) time. So overall it's O(N + L) time.

// OJ: https://leetcode.com/problems/minimum-moves-to-make-array-complementary/
// Author: github.com/lzl124631x
// Time: O(N + L)
// Space: O(L)
// Ref: https://leetcode.com/problems/minimum-moves-to-make-array-complementary/discuss/952773/PythonJava-simple-O(max(n-k))-method
class Solution {
public:
    int minMoves(vector<int>& A, int L) {
        vector<int> delta(2 * L + 2); // difference array
        int N = A.size(), ans = N, cur = 0;
        for (int i = 0; i < N / 2; ++i) {
            int a = A[i], b = A[N - i - 1];
            delta[2] += 2;
            delta[min(a, b) + 1]--;
            delta[a + b]--;
            delta[a + b + 1]++;
            delta[max(a, b) + L + 1]++;
        }
        for (int i = 2; i <= 2 * L; ++i) {
            cur += delta[i];
            ans = min(ans, cur);
        }
        return ans;
    }
};