Problem Description

Given an array nums of even length n and an integer limit, you are to make the array complementary. An array is complementary if for every pair (nums[i], nums[n - 1 - i]) (for all i from 0 to n/2 - 1), the sum is equal to the same value for every pair.

For each pair, you are allowed to change either or both numbers to any integer in the range [1, limit]. Changing a number counts as one move. Return the minimum total moves needed to make the array complementary.

• Each element can be changed multiple times (but only one change per element per pair).
• Constraints: 2 <= n <= 10^5, 1 <= limit <= 10^5, 1 <= nums[i] <= limit, n is even.

Thought Process

At first glance, a brute-force approach would check every possible target sum for all pairs, and for each, count the moves needed. But with large n and limit, this is not feasible.

We need to figure out, for each possible sum S (from 2 to 2 * limit), how many moves it would take to make every pair's sum equal to S. For a pair (a, b), we notice:

• If a + b == S, no moves are needed.
• If we can change one of them to reach S (and it's within [1, limit]), that's one move.
• Otherwise, we need two moves (change both).

This leads us to an interval/difference array approach, where we can efficiently count the number of pairs requiring 0, 1, or 2 moves for each possible sum.

Solution Approach

• We process all pairs (nums[i], nums[n-1-i]) for i from 0 to n/2-1.
• For each pair (a, b):
  • The sum a + b needs 0 moves if we target that sum.
  • We can change one number to get any sum in [min(a, b)+1, max(a, b)+limit] using one move.
  • All other sums require two moves.
• We use a difference array diff of size 2 * limit + 2 to efficiently track, for each possible sum S, the number of additional moves needed.
• For each pair:
  1. Increment diff[2] by 2 (every sum starts with 2 moves by default).
  2. Decrement diff[min(a, b)+1] by 1 (from this point, only 1 move is needed).
  3. Decrement diff[a+b] by 1 (from this point, 0 moves are needed).
  4. Increment diff[a+b+1] by 1 (exit 0 move interval, back to 1 move).
  5. Increment diff[max(a, b)+limit+1] by 1 (exit 1 move interval, back to 2 moves).
• After processing all pairs, take the prefix sum of diff to get the number of moves needed for each possible sum S.
• The answer is the minimum value in this array.

This approach is efficient because it processes all pairs in O(n) time and computes the result for all possible sums in O(limit) time.

Example Walkthrough

Suppose nums = [1,2,4,3], limit = 4. The pairs are (1,3) and (2,4).

• Pair (1,3): a=1, b=3
  • Sum = 4 needs 0 moves.
  • One move can get any sum in [2, 4+4=7].
• Pair (2,4): a=2, b=4
  • Sum = 6 needs 0 moves.
  • One move can get any sum in [3, 4+4=8].

We use the difference array as described. After processing both pairs and computing prefix sums, we find for each possible sum (from 2 to 8) the number of moves required. The minimum is 1, which is the answer.

Time and Space Complexity

• Brute-force: For each possible sum (O(limit)), check every pair (O(n)), so total O(n*limit) — not feasible for large inputs.
• Optimized approach:
  • Processing all pairs: O(n)
  • Building and prefix-summing the difference array: O(limit)
  • Total: O(n + limit)
• Space: The difference array uses O(limit) space.

Summary

We efficiently solve the "Minimum Moves to Make Array Complementary" problem by leveraging a difference array to track the number of moves needed for each possible target sum. By analyzing the range of sums achievable with 0, 1, or 2 moves for each pair, and aggregating this information, we avoid brute-force enumeration and achieve an O(n + limit) solution. This approach highlights the power of interval counting and prefix sums in optimizing problems involving ranges and cumulative effects.

Code Implementation

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):
            a, b = nums[i], nums[n - 1 - i]
            low = 1 + min(a, b)
            high = limit + max(a, b)
            s = a + b

            diff[2] += 2
            diff[low] -= 1
            diff[s] -= 1
            diff[s + 1] += 1
            diff[high + 1] += 1

        res = float('inf')
        curr = 0
        for S in range(2, 2 * limit + 1):
            curr += diff[S]
            res = min(res, curr)
        return res
      

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        vector<int> diff(2 * limit + 2, 0);
        for (int i = 0; i < n / 2; ++i) {
            int a = nums[i], b = nums[n - 1 - i];
            int low = 1 + min(a, b);
            int high = limit + max(a, b);
            int s = a + b;

            diff[2] += 2;
            diff[low] -= 1;
            diff[s] -= 1;
            diff[s + 1] += 1;
            diff[high + 1] += 1;
        }
        int res = INT_MAX, curr = 0;
        for (int S = 2; S <= 2 * limit; ++S) {
            curr += diff[S];
            res = min(res, curr);
        }
        return res;
    }
};
      

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n = nums.length;
        int[] diff = new int[2 * limit + 2];
        for (int i = 0; i < n / 2; ++i) {
            int a = nums[i], b = nums[n - 1 - i];
            int low = 1 + Math.min(a, b);
            int high = limit + Math.max(a, b);
            int s = a + b;

            diff[2] += 2;
            diff[low] -= 1;
            diff[s] -= 1;
            diff[s + 1] += 1;
            diff[high + 1] += 1;
        }
        int res = Integer.MAX_VALUE, curr = 0;
        for (int S = 2; S <= 2 * limit; ++S) {
            curr += diff[S];
            res = Math.min(res, curr);
        }
        return res;
    }
}
      

var minMoves = function(nums, limit) {
    const n = nums.length;
    const diff = new Array(2 * limit + 2).fill(0);
    for (let i = 0; i < n / 2; ++i) {
        const a = nums[i], b = nums[n - 1 - i];
        const low = 1 + Math.min(a, b);
        const high = limit + Math.max(a, b);
        const s = a + b;

        diff[2] += 2;
        diff[low] -= 1;
        diff[s] -= 1;
        diff[s + 1] += 1;
        diff[high + 1] += 1;
    }
    let res = Number.MAX_SAFE_INTEGER, curr = 0;
    for (let S = 2; S <= 2 * limit; ++S) {
        curr += diff[S];
        res = Math.min(res, curr);
    }
    return res;
};