3224. Minimum Array Changes to Make Differences Equal
Description
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 thatabs(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 isnums = [1,2,1,2,4,3]
. - Replace
nums[3]
by 3. The resulting array isnums = [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 isnums = [0,1,2,0,3,6,5,4]
. - Replace
nums[4]
by 4. The resulting array isnums = [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
Solutions
Solution 1: Difference Array
Assume that in the final array, the difference between the pair $\textit{nums}[i]$ and $\textit{nums}[n-i-1]$ is $s$.
Let's denote $x$ as the smaller value between $\textit{nums}[i]$ and $\textit{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 $\textit{nums}$.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|