Minimum array changes to make differences equal

Array Hash Table Prefix Sum

24.3% acceptance

Feb 25, 2026

253

You are given an integer array nums of size n where n is even, and an integer k. You can perform some changes on the array, where in one change you can replace any element in the array with any integer in the range from 0 to k. You need to perform some changes (possibly none) such that the final array satisfies: There exists an integer X such that abs(a[i] - a[n - i - 1]) = X for all (0 <= i < n). Return the minimum number of changes required to satisfy the above condition.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_changes(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let half = n / 2;
    let k = k as usize;

    // freq[d] = # pairs with current diff d
    let mut freq = vec![0i32; k + 1];
    // mr_count[mr] = # pairs with max_reach = mr
    let mut mr_count = vec![0i32; k + 2];

    for i in 0..half {
      let a = nums[i] as usize;
      let b = nums[n - 1 - i] as usize;
      let d = a.abs_diff(b);
      freq[d] += 1;
      // max_reach: max achievable diff with 1 change
      // = max(a, b, k-a, k-b)
      let mr = a.max(b).max(k - a.min(k)).max(k - b.min(k));
      if mr <= k {
        mr_count[mr] += 1;
      } else {
        mr_count[k] += 1;
      }
    }

    // count_2[X] = # pairs with max_reach < X (need 2 changes)
    // = prefix_sum of mr_count up to X-1
    let mut ans = half as i32; // worst case: all 2 changes (X far out of range)

    // For X in [0..=k]:
    // total_changes(X) = half - freq[X] + count_2[X]
    //                  = half - freq[X] + prefix (# pairs with mr < X)
    // prefix here is sum of mr_count[0..X-1]
    let mut count2 = 0i32;
    for x in 0..=k {
      let total = half as i32 - freq[x] + count2;
      if total < ans {
        ans = total;
      }
      count2 += mr_count[x];
    }
    ans
  }
}