Minimum Moves to Make Array Complementary

Problem

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.

Examples

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 <= 10^5
• 1 <= nums[i] <= limit <= 10^5
• n is even.

Solution

Method 1 – Prefix Sum Sweep

Intuition

For each pair (nums[i], nums[n-1-i]), the sum can be made complementary by changing either or both numbers. By analyzing the cost to make each pair sum to every possible target, we can efficiently find the minimum moves using a prefix sum sweep.

Approach

1. For each pair (a, b), calculate:
   • 0 moves if their sum is already the target.
   • 1 move if one of them can be changed to reach the target sum.
   • 2 moves if both need to be changed.
2. Use a difference array to record the cost for each possible sum.
3. Sweep through all possible sums to find the minimum total moves.

Code

C++

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

Go

func minMoves(nums []int, limit int) int {
    n := len(nums)
    diff := make([]int, 2*limit+2)
    for i := 0; i < n/2; i++ {
        a, b := nums[i], nums[n-1-i]
        diff[2] += 2
        diff[min(a, b)+1] -= 1
        diff[a+b] -= 1
        diff[a+b+1] += 1
        diff[max(a, b)+limit+1] += 1
    }
    ans, curr := n, 0
    for s := 2; s <= 2*limit; s++ {
        curr += diff[s]
        if curr < ans {
            ans = curr
        }
    }
    return ans
}
func min(a, b int) int { if a < b { return a } else { return b } }
func max(a, b int) int { if a > b { return a } else { return b } }

Java

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

Kotlin

class Solution {
    fun minMoves(nums: IntArray, limit: Int): Int {
        val n = nums.size
        val diff = IntArray(2 * limit + 2)
        for (i in 0 until n / 2) {
            val a = nums[i]
            val b = nums[n - 1 - i]
            diff[2] += 2
            diff[minOf(a, b) + 1] -= 1
            diff[a + b] -= 1
            diff[a + b + 1] += 1
            diff[maxOf(a, b) + limit + 1] += 1
        }
        var ans = n
        var curr = 0
        for (s in 2..2 * limit) {
            curr += diff[s]
            ans = minOf(ans, curr)
        }
        return ans
    }
}

Python

class Solution:
    def minMoves(self, nums: list[int], limit: int) -> int:
        n: int = len(nums)
        diff: list[int] = [0] * (2 * limit + 2)
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            diff[2] += 2
            diff[min(a, b) + 1] -= 1
            diff[a + b] -= 1
            diff[a + b + 1] += 1
            diff[max(a, b) + limit + 1] += 1
        ans: int = n
        curr: int = 0
        for s in range(2, 2 * limit + 1):
            curr += diff[s]
            ans = min(ans, curr)
        return ans

Rust

impl Solution {
    pub fn min_moves(nums: Vec<i32>, limit: i32) -> i32 {
        let n = nums.len();
        let mut diff = vec![0; (2 * limit + 2) as usize];
        for i in 0..n / 2 {
            let a = nums[i];
            let b = nums[n - 1 - i];
            diff[2] += 2;
            diff[(a.min(b) + 1) as usize] -= 1;
            diff[(a + b) as usize] -= 1;
            diff[(a + b + 1) as usize] += 1;
            diff[(a.max(b) + limit + 1) as usize] += 1;
        }
        let mut ans = n as i32;
        let mut curr = 0;
        for s in 2..=2 * limit {
            curr += diff[s as usize];
            ans = ans.min(curr);
        }
        ans
    }
}

TypeScript

class Solution {
    minMoves(nums: number[], limit: number): number {
        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];
            diff[2] += 2;
            diff[Math.min(a, b) + 1] -= 1;
            diff[a + b] -= 1;
            diff[a + b + 1] += 1;
            diff[Math.max(a, b) + limit + 1] += 1;
        }
        let ans = n, curr = 0;
        for (let s = 2; s <= 2 * limit; ++s) {
            curr += diff[s];
            ans = Math.min(ans, curr);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n + limit), because we process each pair once and then sweep through all possible sums.
• 🧺 Space complexity: O(limit), for the difference array.