3224. Minimum Array Changes to Make Differences Equal LeetCode Solution

In this guide, you will get 3224. Minimum Array Changes to Make Differences Equal LeetCode Solution with the best time and space complexity. The solution to Minimum Array Changes to Make Differences Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Array Changes to Make Differences Equal solution in C++
Minimum Array Changes to Make Differences Equal solution in Java
Minimum Array Changes to Make Differences Equal solution in Python
Additional Resources

3224. Minimum Array Changes to Make Differences Equal LeetCode Solution image

Problem Statement of Minimum Array Changes to Make Differences Equal

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3224. Minimum Array Changes to Make Differences Equal LeetCode Solution in C++

class Solution {
 public:
  int minChanges(vector<int>& nums, int k) {
    const int n = nums.size();
    const int pairSize = n / 2;
    int ans = n;
    unordered_map<int, int> diffCount;  // {abs(nums[-1 - i] - nums[i]): freq}
    // oneChangeCount[i] := the number of pairs that need only one change to to
    // achieve a difference of `i`
    vector<int> oneChangeCount(k + 1);

    for (int i = 0; i < pairSize; ++i) {
      const int a = nums[i];
      const int b = nums[n - 1 - i];
      ++diffCount[abs(a - b)];
      ++oneChangeCount[max({a, b, k - a, k - b})];
    }

    // prefixOneChangeCount[i] := the number of pairs that need only one change
    // to achieve a difference >= `i`
    // prefixOneChangeCount[i] = sum(oneChangeCount[i..k])
    vector<int> prefixOneChangeCount{oneChangeCount};

    for (int i = k - 1; i >= 0; --i)
      prefixOneChangeCount[i] += prefixOneChangeCount[i + 1];

    for (const auto& [diff, freq] : diffCount) {
      const int oneChange = prefixOneChangeCount[diff] - freq;
      const int twoChanges = (pairSize - prefixOneChangeCount[diff]) * 2;
      ans = min(ans, oneChange + twoChanges);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3224. Minimum Array Changes to Make Differences Equal LeetCode Solution in Java

class Solution {
  public int minChanges(int[] nums, int k) {
    final int n = nums.length;
    final int pairSize = n / 2;
    int ans = n;
    Map<Integer, Integer> diffCount = new HashMap<>(); // {abs(nums[-1 - i] - nums[i]): freq}
    // oneChangeCount[i] := the number of pairs that need only one change to
    // achieve a difference of `i`
    int[] oneChangeCount = new int[k + 1];

    for (int i = 0; i < pairSize; ++i) {
      final int a = nums[i];
      final int b = nums[n - 1 - i];
      diffCount.merge(Math.abs(a - b), 1, Integer::sum);
      ++oneChangeCount[Math.max(Math.max(a, b), Math.max(k - a, k - b))];
    }

    // prefixOneChangeCount[i] := the number of pairs that need only one change
    // to achieve a difference >= `i`
    // prefixOneChangeCount[i] = sum(oneChangeCount[i..k])
    int[] prefixOneChangeCount = oneChangeCount.clone();

    for (int i = k - 1; i >= 0; --i)
      prefixOneChangeCount[i] += prefixOneChangeCount[i + 1];

    for (Map.Entry<Integer, Integer> entry : diffCount.entrySet()) {
      final int diff = entry.getKey();
      final int freq = entry.getValue();
      final int oneChange = prefixOneChangeCount[diff] - freq;
      final int twoChanges = (pairSize - prefixOneChangeCount[diff]) * 2;
      ans = Math.min(ans, oneChange + twoChanges);
    }

    return ans;
  }
}
// code provided by PROGIEZ

3224. Minimum Array Changes to Make Differences Equal LeetCode Solution in Python

class Solution:
  def minChanges(self, nums: list[int], k: int) -> int:
    pairSize = len(nums) // 2
    diffCount = collections.Counter()  # {nums[-1 - i] - nums[i]: freq}
    # oneChangeCount[i] := the number of pairs that need only one change to
    # to achieve a difference of `i`
    oneChangeCount = [0] * (k + 1)

    for i in range(pairSize):
      a = nums[i]
      b = nums[-1 - i]
      diffCount[abs(a - b)] += 1
      oneChangeCount[max(a, b, k - a, k - b)] += 1

    # prefixOneChangeCount[i] := the number of pairs that need only one change
    # to achieve a difference >= `i`
    # prefixOneChangeCount[i] = sum(oneChangeCount[i..k])
    prefixOneChangeCount = list(
        itertools.accumulate(reversed(oneChangeCount)))[::-1]

    return min(prefixOneChangeCount[diff] - freq +  # one change
               (pairSize - prefixOneChangeCount[diff]) * 2  # two changes
               for diff, freq in diffCount.items())
 # code by PROGIEZ