Minimum moves to make array complementary

Array Hash Table Prefix Sum

43.3% acceptance

Feb 25, 2026

747

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, nums[i] + nums[n-1-i] equals the same number. Return the minimum number of moves required to make nums complementary.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_moves(nums: Vec<i32>, limit: i32) -> i32 {
    let n = nums.len();
    let limit = limit as usize;
    // diff[T] = total savings from baseline (each pair costs 2 by default)
    // Size: 2*limit + 2 (T ranges from 2 to 2*limit)
    let mut diff = vec![0i32; 2 * limit + 3];
    let baseline = (n / 2 * 2) as i32;

    for i in 0..n / 2 {
      let lo = nums[i].min(nums[n - 1 - i]) as usize;
      let hi = nums[i].max(nums[n - 1 - i]) as usize;
      // Since 1 <= lo <= hi <= limit, the union [lo+1, lo+limit] ∪ [hi+1, hi+limit]
      // always merges into [lo+1, hi+limit] (no gap is possible).
      // Save 1 for the entire union range [lo+1, hi+limit]
      diff[lo + 1] -= 1;
      diff[hi + limit + 1] += 1;
      // Save 1 more at T = lo+hi (no change needed)
      diff[lo + hi] -= 1;
      diff[lo + hi + 1] += 1;
    }

    let mut min_cost = baseline;
    let mut acc = 0i32;
    for t in 2..=2 * limit {
      acc += diff[t];
      min_cost = min_cost.min(baseline + acc);
    }
    min_cost
  }
}