1674. Minimum Moves to Make Array Complementary LeetCode Solution
In this guide, you will get 1674. Minimum Moves to Make Array Complementary LeetCode Solution with the best time and space complexity. The solution to Minimum Moves to Make Array Complementary 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 of Minimum Moves to Make Array Complementary
You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.
The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n – 1 – i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n – 1 – i] = 5.
Return the minimum number of moves required to make nums complementary.
Example 1:
Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
Example 2:
Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.
n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 105
n is even.
Complexity Analysis
Time Complexity: O(n + \texttt{limit})
Space Complexity: O(\texttt{limit})
1674. Minimum Moves to Make Array Complementary LeetCode Solution in C++
class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
const int n = nums.size();
int ans = n;
// delta[i] := the number of moves needed when target goes from i - 1 to i
vector<int> delta(limit * 2 + 2);
for (int i = 0; i < n / 2; ++i) {
const int a = nums[i];
const int b = nums[n - 1 - i];
--delta[min(a, b) + 1];
--delta[a + b];
++delta[a + b + 1];
++delta[max(a, b) + limit + 1];
}
// Initially, we need `moves` when the target is 2.
for (int i = 2, moves = n; i <= limit * 2; ++i) {
moves += delta[i];
ans = min(ans, moves);
}
return ans;
}
}; /* code provided by PROGIEZ */
1674. Minimum Moves to Make Array Complementary LeetCode Solution in Java
class Solution {
public int minMoves(int[] nums, int limit) {
final int n = nums.length;
int ans = n;
// delta[i] := the number of moves needed when target goes from i - 1 to i
int[] delta = new int[limit * 2 + 2];
for (int i = 0; i < n / 2; ++i) {
final int a = nums[i];
final int b = nums[n - 1 - i];
--delta[Math.min(a, b) + 1];
--delta[a + b];
++delta[a + b + 1];
++delta[Math.max(a, b) + limit + 1];
}
// Initially, we need `moves` when the target is 2.
for (int i = 2, moves = n; i <= limit * 2; ++i) {
moves += delta[i];
ans = Math.min(ans, moves);
}
return ans;
}
} // code provided by PROGIEZ
1674. Minimum Moves to Make Array Complementary LeetCode Solution in Python
class Solution:
def minMoves(self, nums: list[int], limit: int) -> int:
n = len(nums)
ans = n
# delta[i] := the number of moves needed when target goes from i - 1 to i
delta = [0] * (limit * 2 + 2)
for i in range(n // 2):
a = nums[i]
b = nums[n - 1 - i]
delta[min(a, b) + 1] -= 1
delta[a + b] -= 1
delta[a + b + 1] += 1
delta[max(a, b) + limit + 1] += 1
# Initially, we need `moves` when the target is 2.
moves = n
for i in range(2, limit * 2 + 1):
moves += delta[i]
ans = min(ans, moves)
return ans # code by PROGIEZ
