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:
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:
nums[1] by 2. The resulting array is nums = [1,2,1,2,4,3].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:
nums[3] by 0. The resulting array is nums = [0,1,2,0,3,6,5,4].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 <= 105n is even.0 <= nums[i] <= k <= 105Problem Overview: You have an array nums and a value range [0, k]. For every symmetric pair (i, n-1-i), the difference is |nums[i] - nums[n-1-i]|. You may change any element to any value in [0, k]. The goal is to make every pair produce the same absolute difference while minimizing the number of element changes.
Approach 1: Frequency of Absolute Differences (O(n * k) time, O(k) space)
Process the array as symmetric pairs. For each pair (a, b), compute the current difference d = |a - b|. If you choose a target difference x, the pair may require 0, 1, or 2 changes. Zero changes if x == d. One change is possible if you can modify either element within [0, k] to achieve difference x. Otherwise two changes are required. By iterating through every possible target difference x from 0..k and evaluating each pair, you compute the total cost. A hash table or array tracks frequencies of existing differences. This approach directly models the rules but becomes slow when k is large because every target difference checks every pair.
Approach 2: Optimize with Frequency Arrays (O(n + k) time, O(k) space)
Instead of recalculating the cost per pair for every possible difference, precompute how each pair behaves across the range of differences. For a pair (a, b), compute its current difference d and the maximum difference reachable with a single modification: maxOne = max(max(a, k-a), max(b, k-b)). If the target difference is exactly d, the cost is 0. If the target difference is ≤ maxOne, you can reach it with one change. Otherwise two changes are required. Maintain a frequency array for exact differences and another prefix structure that tracks how many pairs allow a one-change solution up to each difference value.
For each candidate difference x, compute the total cost using aggregated counts: pairs already equal to x cost 0, pairs that can reach x with one change cost 1, and the remaining pairs cost 2. Prefix sums make this calculation constant time per difference. The algorithm scans the difference range once, producing an overall O(n + k) solution.
This optimization relies heavily on counting techniques and prefix accumulation, common in problems involving range updates or cost aggregation. Related techniques appear in array, hash table, and prefix sum problems where precomputation converts repeated work into constant-time queries.
Recommended for interviews: The frequency-array + prefix-sum approach. Interviewers expect you to first reason about how many changes each pair needs (0, 1, or 2). The optimized counting step shows strong algorithmic thinking because it reduces repeated pair evaluation into a single aggregated pass over the difference range.
Approach: For each pair (i, n-i-1), calculate their absolute difference. Build a frequency table for these differences. The key is to determine the most common difference, which will require the least changes to make all pairs have the same difference. You can replace elements within the pair by any integer in the range 0 to k.
Explanation: The provided Python solution iterates through the first half of the array to create difference pairs. It uses a dictionary to count how often each difference occurs. Finally, it calculates the minimum number of changes needed by transforming the most common difference across as many pairs as possible, reducing unnecessary changes.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(n), primarily due to the data structure used for counting differences.
Approach: Instead of using a hashmap which could grow large, use arrays to keep track of the counts of differences. This is practically efficient when k is small or manageable and provides faster operations on indices which are naturally bounded by k.
Explanation: The C solution utilizes an integer array to count differences directly using array indices. It iterates through pairs, calculates their difference, and increments the count at the respective index in the diff_count array. This avoids collisions and provides efficient direct access.
Time Complexity: O(n).
Space Complexity: O(k) where k is the range of possible differences.
Assume that in the final array, the difference between the pair nums[i] and nums[n-i-1] is s.
Let's denote x as the smaller value between nums[i] and nums[n-i-1], and y as the larger value.
For each pair of numbers, we have the following scenarios:
y - x = s.s \le max(y, k - x), where the maximum value is achieved by changing x to 0, or changing y to k.s > max(y, k - x).That is:
[0, y-x-1], 1 change is needed.[y-x], no change is needed.[y-x+1, max(y, k-x)], 1 change is needed.[max(y, k-x)+1, k], 2 changes are needed.We enumerate each pair of numbers and use a difference array to update the number of changes needed in different ranges for each pair.
Finally, we find the minimum value among the prefix sums from the difference array, which is the minimum number of changes needed.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Similar problems:
| Approach | Complexity |
|---|---|
| Frequency of Absolute Differences | Time Complexity: O(n) where n is the length of the array. |
| Optimize with Frequency Arrays | Time Complexity: O(n). |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency of Absolute Differences | O(n * k) | O(k) | Useful for understanding how pair costs work before optimizing |
| Frequency Arrays + Prefix Sum Optimization | O(n + k) | O(k) | Best general solution when k can be large and many pairs must be evaluated |
3224. Minimum Array Changes to Make Differences Equal | Prefix Sums | Why not Greedy • Aryan Mittal • 7,795 views views
Watch 7 more video solutions →Practice Minimum Array Changes to Make Differences Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor