Scale Engineer

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

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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem