1674. Minimum Moves to Make Array Complementary

Array
Prefix Sum

TIME

O(n + limit)

SPACE

O(limit)

Intuition

For each mirrored pair (a, b), every target sum from 2 to 2 * limit has a cost:

0 moves if the target is a + b
1 move if changing one value can reach the target
2 moves otherwise

The one-move range is:

1 + min(a, b) through limit + max(a, b)

So we can use a difference array over possible sums and add each pair's cost contribution as ranges.

Approach

For each pair (a, b):

Start with cost 2 for all possible sums.
Subtract 1 over the one-move range:
- [1 + min(a, b), limit + max(a, b)]
Subtract another 1 at the exact current sum:
- [a + b, a + b]

After processing all pairs, prefix-sum the difference array. The minimum value over sums 2..2 * limit is the answer.

Complexity

Time: O(n + limit)
Space: O(limit)

Edge Cases

Already complementary -> some target sum has cost 0
limit is small -> valid sums are still only 2..2 * limit
Duplicate pair sums -> exact-sum zero-move updates accumulate

Code

from typing import List


class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        """
        1674. Minimum Moves to Make Array Complementary
        Time: O(n + limit)
        Space: O(limit)
        """
        diff = [0] * (2 * limit + 2)
        n = len(nums)

        for i in range(n // 2):
            a = nums[i]
            b = nums[n - 1 - i]
            low = 1 + min(a, b)
            high = limit + max(a, b)
            total = a + b

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

        answer = n
        moves = 0

        for target in range(2, 2 * limit + 1):
            moves += diff[target]
            answer = min(answer, moves)

        return answer

/**
 * 1674. Minimum Moves to Make Array Complementary
 * Time: O(n + limit)
 * Space: O(limit)
 */
class Solution {
    public int minMoves(int[] nums, int limit) {
        int[] diff = new int[2 * limit + 2];
        int n = nums.length;

        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];
            int low = 1 + Math.min(a, b);
            int high = limit + Math.max(a, b);
            int total = a + b;

            diff[2] += 2;
            diff[low] -= 1;
            diff[high + 1] += 1;
            diff[total] -= 1;
            diff[total + 1] += 1;
        }

        int answer = n;
        int moves = 0;

        for (int target = 2; target <= 2 * limit; target++) {
            moves += diff[target];
            answer = Math.min(answer, moves);
        }

        return answer;
    }
}