Skip to main content
Talentd

Minimum Array Changes to Make Differences Equal - Solution & Explanation

MediumArrayHash TablePrefix Sum16 min readAsked at: Airbus, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Frequency of Absolute Differences

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Optimize with Frequency Arrays

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.

Code

CC++

C

C++

Complexity

Time Complexity: O(n).
Space Complexity: O(k) where k is the range of possible differences.

Try this approach in the editor →

Approach 3: Difference Array

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:

  • If no change is needed, then y - x = s.
  • If one change is made, then s \le max(y, k - x), where the maximum value is achieved by changing x to 0, or changing y to k.
  • If two changes are made, then s > max(y, k - x).

That is:

  • In the range [0, y-x-1], 1 change is needed.
  • At [y-x], no change is needed.
  • In the range [y-x+1, max(y, k-x)], 1 change is needed.
  • In the range [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:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency of Absolute Differences

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.

Optimize with Frequency Arrays

Time Complexity: O(n).
Space Complexity: O(k) where k is the range of possible differences.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency of Absolute DifferencesO(n * k)O(k)Useful for understanding how pair costs work before optimizing
Frequency Arrays + Prefix Sum OptimizationO(n + k)O(k)Best general solution when k can be large and many pairs must be evaluated

Video Solution

3224. Minimum Array Changes to Make Differences Equal | Prefix Sums | Why not Greedy • Aryan Mittal • 7,924 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Array Changes to Make Differences Equal easy or hard?
Minimum Array Changes to Make Differences Equal is generally rated Medium difficulty. The challenge is recognizing that each pair contributes a cost of 0, 1, or 2 changes depending on the target difference and then aggregating these costs efficiently using prefix sums.
Minimum Array Changes to Make Differences Equal Python/Java solution
Typical implementations use arrays to store frequency counts and prefix sums. Python and Java solutions both iterate through symmetric pairs, compute the reachable difference range, update frequency arrays, and then scan all possible differences to compute the minimum cost in O(n + k) time.
How to solve Minimum Array Changes to Make Differences Equal in O(n)?
Process the array as n/2 symmetric pairs and compute their current difference and the maximum difference reachable with one change. Use frequency arrays to track exact matches and prefix sums to track one-change feasibility. This allows computing the total cost for each candidate difference in constant time, giving O(n + k) complexity.
What is the best approach for Minimum Array Changes to Make Differences Equal?
The most efficient approach uses frequency arrays combined with prefix sums. For each symmetric pair you compute the current difference and the maximum difference achievable with one modification. Aggregating these values allows you to evaluate the cost of every target difference in O(1) time, resulting in an overall O(n + k) algorithm.
Is Minimum Array Changes to Make Differences Equal asked at Google/Amazon/Meta?
Problems combining pair processing, difference constraints, and prefix-sum optimization appear frequently in interviews at large companies like Google, Amazon, and Meta. While this exact question is from LeetCode, the counting and cost-aggregation technique is commonly tested in system design and algorithm interviews.
What data structure is used in Minimum Array Changes to Make Differences Equal?
The core data structures are frequency arrays and prefix sums. These structures track how many pairs already match a difference and how many can reach a difference with one modification, enabling fast cost calculations for each candidate difference.
What is the time complexity of Minimum Array Changes to Make Differences Equal?
The optimized solution runs in O(n + k) time where n is the array length and k is the maximum allowed value. The array is scanned once to process symmetric pairs, and then the difference range 0..k is evaluated using prefix sums. Space complexity is O(k) for the frequency arrays.

Ready to solve this problem?

Practice Minimum Array Changes to Make Differences Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays