Minimum Array Changes to Make Differences Equal

Med

#2863Time: 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.1 company

Patterns

Prefix Sum

Data structures

Array Hash Table

Companies

Airbus SE

Prompt

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 <= 10⁵
n is even.
0 <= nums[i] <= k <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int minChanges(int[] nums, int k) {3        int n = nums.length;4        int minTotalChanges = n; // Maximum possible changes5 6        for (int X = 0; X <= k; X++) {7            int currentChanges = 0;8            for (int i = 0; i < n / 2; i++) {9                int a = nums[i];10                int b = nums[n - 1 - i];11 12                if (Math.abs(a - b) == X) {13                    // 0 changes needed14                    continue;15                } else {16                    int maxDiffOneChange = Math.max(Math.max(a, k - a), Math.max(b, k - b));17                    if (X <= maxDiffOneChange) {18                        // 1 change is sufficient19                        currentChanges += 1;20                    } else {21                        // 2 changes are required22                        currentChanges += 2;23                    }24                }25            }26            minTotalChanges = Math.min(minTotalChanges, currentChanges);27        }28 29        return minTotalChanges;30    }31}

Complexity

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.

Trade-offs

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.

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.

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

Walkthrough

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:

Add 1 to TotalSavings[X] for all X in [0, m]. This is a range update.
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.

1class Solution {2    public int minChanges(int[] nums, int k) {3        int n = nums.length;4        int[] delta = new int[k + 2];5 6        for (int i = 0; i < n / 2; i++) {7            int a = nums[i];8            int b = nums[n - 1 - i];9 10            // To simplify, let u <= v11            int u = Math.min(a, b);12            int v = Math.max(a, b);13 14            // Original difference15            int diff = v - u;16 17            // Max difference achievable with one change18            // max_diff = max(v, k-u)19            int maxDiffOneChange = Math.max(v, k - u);20 21            // Cost is 2 by default. 22            // Savings of 1 for X in [0, maxDiffOneChange]23            // Additional saving of 1 for X = diff24 25            // Update for saving of 1 over range [0, maxDiffOneChange]26            delta[0] += 1;27            delta[maxDiffOneChange + 1] -= 1;28 29            // Update for additional saving of 1 at point diff30            delta[diff] += 1;31            delta[diff + 1] -= 1;32        }33 34        int maxSavings = 0;35        int currentSavings = 0;36        for (int x = 0; x <= k; x++) {37            currentSavings += delta[x];38            maxSavings = Math.max(maxSavings, currentSavings);39        }40 41        // Total changes for n/2 pairs is n by default (2 per pair)42        return n - maxSavings;43    }44}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minChanges(int[] nums, int k) {4    int[] d = new int[k + 2];5    int n = nums.length;6    for (int i = 0; i < n / 2; ++i) {7      int x = Math.min(nums[i], nums[n - i - 1]);8      int y = Math.max(nums[i], nums[n - i - 1]);9      d[0] += 1;10      d[y - x] -= 1;11      d[y - x + 1] += 1;12      d[Math.max(y, k - x) + 1] -= 1;13      d[Math.max(y, k - x) + 1] += 2;14    }15    int ans = n, s = 0;16    for (int x : d) {17      s += x;18      ans = Math.min(ans, s);19    }20    return ans;21  }22}

1class Solution {2public:3  int minChanges(vector<int> &nums, int k) {4    int d[k + 2];5    memset(d, 0, sizeof(d));6    int n = nums.size();7    for (int i = 0; i < n / 2; ++i) {8      int x = min(nums[i], nums[n - i - 1]);9      int y = max(nums[i], nums[n - i - 1]);10      d[0] += 1;11      d[y - x] -= 1;12      d[y - x + 1] += 1;13      d[max(y, k - x) + 1] -= 1;14      d[max(y, k - x) + 1] += 2;15    }16    int ans = n, s = 0;17    for (int x : d) {18      s += x;19      ans = min(ans, s);20    }21    return ans;22  }23};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem