Problem

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 the following condition:

  • 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: nums = [1,0,1,2,4,3], k = 4

Output: 2

Explanation:  
We can perform the following changes:

  * Replace `nums[1]` by 2. The resulting array is `nums = [1,_**2**_ ,1,2,4,3]`.
  * Replace `nums[3]` by 3. The resulting array is `nums = [1,2,1,_**3**_ ,4,3]`.

The integer `X` will be 2.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: nums = [0,1,2,3,3,6,5,4], k = 6

Output: 2

Explanation:  
We can perform the following operations:

  * Replace `nums[3]` by 0. The resulting array is `nums = [0,1,2,_**0**_ ,3,6,5,4]`.
  * Replace `nums[4]` by 4. The resulting array is `nums = [0,1,2,0,**_4_** ,6,5,4]`.

The integer `X` will be 4.

Constraints

  • 2 <= n == nums.length <= 10^5
  • n is even.
  • 0 <= nums[i] <= k <= 10^5

Solution

Method 1 – Hash Map + Frequency Counting

Intuition

For each pair (a[i], a[n-i-1]), the difference must be the same for all i. To minimize changes, count the frequency of each possible difference and choose the most frequent one. For each pair, if their difference is not the target, we can change either element to any value in [0, k] to achieve the target difference.

Approach

  1. For each i in [0, n//2), compute all possible differences for (nums[i], nums[n-i-1]) and count their frequencies.
  2. For each possible difference X, calculate the minimum changes needed to make all pairs have difference X.
  3. For each pair, if their difference is already X, no change is needed. Otherwise, one change is enough since we can set either element to any value in [0, k].
  4. Return the minimum changes over all possible X.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def min_array_changes(nums: list[int], k: int) -> int:
    from collections import Counter
    n = len(nums)
    freq = Counter()
    for i in range(n//2):
        a, b = nums[i], nums[n-i-1]
        freq[abs(a-b)] += 1
    min_changes = n//2
    for x in range(k+1):
        changes = n//2 - freq[x]
        min_changes = min(min_changes, changes)
    return min_changes

Complexity

  • ⏰ Time complexity: O(n + k)
    • Counting pairs and iterating over possible differences.
  • 🧺 Space complexity: O(k)
    • For frequency map.