Notebook

1674. Minimum Moves to Make Array Complementary

Brute force over all target sums is O(n²) — learn how a difference array over pair ranges collapses it to O(n log n).

3 min read ArrayDifference Array

Problem Statement

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, [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

Example 1

Input: nums = [1,2,4,3], limit = 4
Output: 1

Explanation: Change nums to [1,2,2,3]. Now every pair sums to 4.

Example 2

Input: nums = [1,2,2,1], limit = 2
Output: 2

Example 3

Input: nums = [1,2,1,2], limit = 2
Output: 0

Explanation: Already complementary.

Constraints

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

Explanation

Brute force

For each pair (i, n-i-1), just check how many moves every other pair would need to match that sum. That’s O(n²) — too slow for n = 10^5.

Optimal

The idea is to think about what target sum S minimizes total moves across all pairs.

For a pair (a, b) where a = nums[i], b = nums[n-i-1]:

  • If S == a + b → 0 moves needed, it’s already there.
  • If min(a,b) + 1 <= S <= max(a,b) + limit → 1 move is enough. We can replace just one of them to hit S.
  • Anything outside that range → 2 moves, we have to replace both.

So for every possible sum S in [2, 2*limit], we want to accumulate the total moves. This is basically offline range updates — perfect for a difference array.

For each pair, we:

  1. Start everything at 2 moves (default).
  2. Subtract 1 for the 1-move range [min+1, max+limit].
  3. Subtract 1 more for the 0-move point [a+b, a+b].

Then take a prefix sum and find the minimum.

Code

#define ll long long
class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        map<ll, int> mp;

        for (int i = 0; i < n / 2; i++) {
            int mn = min(nums[i], nums[n-i-1]) + 1;
            int mx = max(nums[i], nums[n-i-1]) + limit;
            int sm = nums[i] + nums[n-i-1];

            mp[2] += 2;
            mp[2*limit+1] -= 1; // default: 2 moves for everything

            mp[mn] -= 1;
            mp[mx+1] += 1; // 1 move in this range

            mp[sm] -= 1;
            mp[sm+1] += 1; // 0 moves at exact sum
        }

        ll sum = 0, ans = n;
        for (auto &[i, j] : mp) {
            sum += j;
            ans = min(ans, sum);
        }
        return ans;
    }
};

Resources