Watch 8 video solutions for Minimum Array Changes to Make Differences Equal, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by Aryan Mittal has 7,795 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 | 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 |