357. Minimum Moves to Make Array Complementary

For each pair (a, b), choosing target T costs 0 moves if a+b==T, 1 move if T is in [min(a,b)+1, max(a,b)+limit], and 2 moves otherwise. Use a difference array to mark cost transitions across all possible T values, then sweep with a prefix sum to find the T that minimizes total moves.

Approach

Use a difference array to efficiently count the cost of every possible target sum T.

1. Pair up elements: for each i from 0 to n/2 - 1, let a = nums[i], b = nums[n-1-i].
2. For each pair (a, b), choosing a target sum T costs:
   • 0 moves if a + b == T (already correct).
   • 1 move if T is in [min(a,b)+1, max(a,b)+limit] (change one element to make the pair sum to T).
   • 2 moves otherwise (must change both elements).
3. Instead of checking every T for every pair, record transitions in a difference array diff of size 2*limit + 2:
   • diff[2] += 2, diff[2*limit+1] -= 2 — assume 2 moves everywhere.
   • diff[lo] -= 1, diff[hi+1] += 1 — subtract 1 move in the 1-move range [lo, hi] where lo = min(a,b)+1, hi = max(a,b)+limit.
   • diff[s] -= 1, diff[s+1] += 1 — subtract 1 more move at the 0-move point s = a+b.
4. Sweep with a prefix sum over diff[2..2*limit], track the minimum.

Walk-through

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

Pairs: (1,3) and (2,4).

Pair (1,3): s=4, lo=2, hi=7

• 2 moves for T in [2,8], minus 1 for [2,7], minus 1 more at T=4.
• Net: 0 moves at T=4, 1 move for T in [2,3] and [5,7], 2 moves outside.

Pair (2,4): s=6, lo=3, hi=8

• 0 moves at T=6, 1 move for T in [3,5] and [7,8], 2 outside.

Combined cost per T: T=4 gives 0+1=1, T=5 gives 1+1=2, T=6 gives 1+0=1. Minimum is 1.

Why it works

The difference array lets us add cost ranges for all n/2 pairs in O(1) per pair, then a single prefix-sum sweep finds the cheapest target. Total work: O(n + limit).

Edge cases

• Already complementary: every pair sums to the same value, answer is 0.
• limit = 1: all elements are 1, all pairs sum to 2, answer is 0.

import java.util.*;

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 lo = Math.min(a, b) + 1;
            int hi = Math.max(a, b) + limit;
            int s = a + b;
            diff[2] += 2;
            diff[2 * limit + 1] -= 2;
            diff[lo] -= 1;
            diff[hi + 1] += 1;
            diff[s] -= 1;
            diff[s + 1] += 1;
        }
        int result = n, curr = 0;
        for (int t = 2; t <= 2 * limit; t++) {
            curr += diff[t];
            result = Math.min(result, curr);
        }
        return result;
    }
}