# Minimum Array Changes to Make Differences Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-array-changes-to-make-differences-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-array-changes-to-make-differences-equal
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Airbus SE](https://scaleengineer.com/companies/airbus-se)
---
## 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.

**Example 1:**

**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:**

**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 <= 105`
* `n` is even.
* `0 <= nums[i] <= k <= 105`

# Approaches
## Brute-Force by Iterating All Possible Differences
This approach directly translates the problem statement into a solution. We test every possible value for the final difference `X`, which can range from `0` to `k`. For each potential `X`, we calculate the total number of modifications needed across all `n/2` pairs of elements `(nums[i], nums[n-1-i])`. The minimum of these totals over all `X` is our answer.
**Time:** O(n * k). The outer loop runs `k+1` times, and the inner loop runs `n/2` times. This results in a total time complexity proportional to `n * k`. · **Space:** O(1) extra space.
**Pros:** Simple to understand and implement.; Correctly solves the problem for smaller constraints.
**Cons:** The time complexity of `O(n * k)` is too high for the given constraints (`n, k <= 10^5`), leading to a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
For each pair of elements `(a, b)` and a target difference `X`, we need to find the minimum changes to make `abs(a' - b') = X`, where `a'` and `b'` are the new values in the range `[0, k]`. The cost is determined as follows:

- **0 changes:** If the original difference `abs(a - b)` is already equal to `X`.
- **1 change:** If `abs(a - b) != X`, but we can change either `a` or `b` to satisfy the condition. By changing one element (say `a` to `a'`), the range of achievable differences is `[0, max(b, k-b)]`. Considering changes to both `a` and `b`, the maximum difference we can achieve with one change is `max(a, b, k-a, k-b)`. If `X` is less than or equal to this maximum, one change is sufficient.
- **2 changes:** If both 0 and 1 change are not possible, we can always achieve the difference `X` with two changes (e.g., by setting one element to `0` and the other to `X`, both of which are valid values in `[0, k]`).

The algorithm iterates through all `X` from `0` to `k`, computes the total cost for each `X` by summing up the costs for all `n/2` pairs, and returns the minimum total cost found.

```java
class Solution {
    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int minTotalChanges = n; // Maximum possible changes

        for (int X = 0; X <= k; X++) {
            int currentChanges = 0;
            for (int i = 0; i < n / 2; i++) {
                int a = nums[i];
                int b = nums[n - 1 - i];

                if (Math.abs(a - b) == X) {
                    // 0 changes needed
                    continue;
                } else {
                    int maxDiffOneChange = Math.max(Math.max(a, k - a), Math.max(b, k - b));
                    if (X <= maxDiffOneChange) {
                        // 1 change is sufficient
                        currentChanges += 1;
                    } else {
                        // 2 changes are required
                        currentChanges += 2;
                    }
                }
            }
            minTotalChanges = Math.min(minTotalChanges, currentChanges);
        }

        return minTotalChanges;
    }
}
```
### Algorithm
- Initialize `min_changes` to a very large number (e.g., `n`).
- Iterate through each possible target difference `X` from `0` to `k`.
- For each `X`, calculate the total changes required:
  - Initialize `current_changes` to `0`.
  - Iterate through each pair of elements `(a, b) = (nums[i], nums[n - 1 - i])` for `i` from `0` to `n/2 - 1`.
  - Determine the cost for the current pair to achieve the difference `X`:
    - If `abs(a - b) == X`, the cost is `0` (no changes needed).
    - Otherwise, check if one change is sufficient. This is possible if `X` is within the range of differences achievable by changing one element. The maximum achievable difference with one change is `max_diff = max(a, b, k - a, k - b)`. If `X <= max_diff`, the cost is `1`.
    - Otherwise, two changes are required, so the cost is `2`.
  - Add the pair's cost to `current_changes`.
- After iterating through all pairs, update `min_changes = min(min_changes, current_changes)`.
- After checking all possible `X`, `min_changes` will hold the minimum number of changes required.

## Difference Array and Prefix Sum
The brute-force approach is inefficient because it repeatedly calculates costs. A more optimal method analyzes how the cost for each pair contributes to the total cost across all possible differences `X`. We can observe that for a single pair, the number of changes required is either 0, 1, or 2, and this value only changes at specific thresholds of `X`. Instead of calculating the total cost for each `X` from scratch, we can calculate the contribution of each pair to all possible `X` values at once. This can be done efficiently using a difference array to handle the range updates corresponding to cost savings.
**Time:** O(n + k). We iterate through `n/2` pairs once to populate the difference array, which takes `O(n)`. Then, we iterate through the difference array of size `k` to compute prefix sums and find the maximum, which takes `O(k)`. · **Space:** O(k) to store the difference array and the computed savings.
**Pros:** Highly efficient with a linear time complexity.; Passes the given constraints with ease.
**Cons:** The logic is more complex than the brute-force approach, involving concepts like difference arrays and prefix sums.; Requires extra space proportional to `k`.
### Explanation
Let's analyze the cost for a single pair `(a, b)`. The default cost is 2 changes. We get 'savings' on this cost. 
- We save 1 change if the target difference `X` can be achieved with one modification. This is possible for any `X` in the range `[0, m]`, where `m = max(a, b, k-a, k-b)`.
- We save an additional 1 change if the target `X` is equal to the pair's original difference `d = abs(a-b)`.

So, for a given `X`, the total savings is the sum of savings from all pairs. `TotalSavings(X) = sum_pairs(I(X <= m) + I(X == d))`, where `I` is the indicator function. The total cost is `n - TotalSavings(X)`. Our goal is to find `max(TotalSavings(X))`. 

We can compute the `TotalSavings` array efficiently. For each pair, we have two updates:
1. Add 1 to `TotalSavings[X]` for all `X` in `[0, m]`. This is a range update.
2. Add 1 to `TotalSavings[X]` for `X = d`. This is a point update.

A difference array (or prefix sum technique) is perfect for handling many range updates. We create a `delta` array. A range update `[L, R]` is done by `delta[L]++` and `delta[R+1]--`. A point update at `P` is a range update `[P, P]`. After processing all pairs, we compute the prefix sum of `delta` to get the final `TotalSavings` array. The maximum value in this array gives us the maximum savings, which leads to the minimum changes.

```java
class Solution {
    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int[] delta = new int[k + 2];

        for (int i = 0; i < n / 2; i++) {
            int a = nums[i];
            int b = nums[n - 1 - i];

            // To simplify, let u <= v
            int u = Math.min(a, b);
            int v = Math.max(a, b);

            // Original difference
            int diff = v - u;

            // Max difference achievable with one change
            // max_diff = max(v, k-u)
            int maxDiffOneChange = Math.max(v, k - u);

            // Cost is 2 by default. 
            // Savings of 1 for X in [0, maxDiffOneChange]
            // Additional saving of 1 for X = diff

            // Update for saving of 1 over range [0, maxDiffOneChange]
            delta[0] += 1;
            delta[maxDiffOneChange + 1] -= 1;

            // Update for additional saving of 1 at point diff
            delta[diff] += 1;
            delta[diff + 1] -= 1;
        }

        int maxSavings = 0;
        int currentSavings = 0;
        for (int x = 0; x <= k; x++) {
            currentSavings += delta[x];
            maxSavings = Math.max(maxSavings, currentSavings);
        }

        // Total changes for n/2 pairs is n by default (2 per pair)
        return n - maxSavings;
    }
}
```
### Algorithm
- The cost for any pair to achieve a difference `X` is `2` by default. This cost can be reduced.
- If `X` can be achieved with one change, the cost becomes `1` (a saving of 1). This is true for `X <= max(a, b, k-a, k-b)`.
- If `X` is the original difference, the cost becomes `0` (an additional saving of 1).
- The total cost for a difference `X` is `(n/2 * 2) - TotalSavings(X)`. To minimize cost, we must maximize savings.
- We can calculate `TotalSavings(X)` for all `X` simultaneously using a difference array.
- **Steps:**
  1. Initialize a difference array `delta` of size `k + 2` to all zeros.
  2. For each pair `(a, b)`:
     a. Calculate `d = abs(a - b)` and `m = max(a, b, k-a, k-b)`.
     b. A saving of 1 applies to all `X` in `[0, m]`. We register this range update in the difference array: `delta[0]++` and `delta[m + 1]--`.
     c. An additional saving of 1 applies at `X = d`. We register this point update: `delta[d]++` and `delta[d + 1]--`.
  3. After processing all pairs, compute the prefix sum of `delta` to get the `savings` array. `savings[X]` will store the total savings for difference `X`.
  4. Find the maximum value `max_savings` in the `savings` array.
  5. The minimum number of changes is `n - max_savings` (since each of the `n/2` pairs requires 2 changes by default, for a total of `n` changes).

# Solutions
### Java

```java
class Solution {
public
  int minChanges(int[] nums, int k) {
    int[] d = new int[k + 2];
    int n = nums.length;
    for (int i = 0; i < n / 2; ++i) {
      int x = Math.min(nums[i], nums[n - i - 1]);
      int y = Math.max(nums[i], nums[n - i - 1]);
      d[0] += 1;
      d[y - x] -= 1;
      d[y - x + 1] += 1;
      d[Math.max(y, k - x) + 1] -= 1;
      d[Math.max(y, k - x) + 1] += 2;
    }
    int ans = n, s = 0;
    for (int x : d) {
      s += x;
      ans = Math.min(ans, s);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minChanges(vector<int> &nums, int k) {
    int d[k + 2];
    memset(d, 0, sizeof(d));
    int n = nums.size();
    for (int i = 0; i < n / 2; ++i) {
      int x = min(nums[i], nums[n - i - 1]);
      int y = max(nums[i], nums[n - i - 1]);
      d[0] += 1;
      d[y - x] -= 1;
      d[y - x + 1] += 1;
      d[max(y, k - x) + 1] -= 1;
      d[max(y, k - x) + 1] += 2;
    }
    int ans = n, s = 0;
    for (int x : d) {
      s += x;
      ans = min(ans, s);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minChanges(self, nums: List[int], k: int) -> int: d = [0] * (k + 2) n = len(nums) for i in range(n // 2): x, y = nums[i], nums[- i - 1] if x > y: x, y = y, x d[0] += 1 d[y - x] -= 1 d[y - x + 1] += 1 d[max(y, k - x) + 1] -= 1 d[max(y, k - x) + 1] += 2 return min(accumulate(d))

```