Minimum Operations to Make Array Equal II
MedPrompt
You are given two integer arrays nums1 and nums2 of equal length n and an integer k. You can perform the following operation on nums1:
- Choose two indexes
iandjand incrementnums1[i]bykand decrementnums1[j]byk. In other words,nums1[i] = nums1[i] + kandnums1[j] = nums1[j] - k.
nums1 is said to be equal to nums2 if for all indices i such that 0 <= i < n, nums1[i] == nums2[i].
Return the minimum number of operations required to make nums1 equal to nums2. If it is impossible to make them equal, return -1.
Example 1:
Input: nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
Output: 2
Explanation: In 2 operations, we can transform nums1 to nums2.
1st operation: i = 2, j = 0. After applying the operation, nums1 = [1,3,4,4].
2nd operation: i = 2, j = 3. After applying the operation, nums1 = [1,3,7,1].
One can prove that it is impossible to make arrays equal in fewer operations.Example 2:
Input: nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
Output: -1
Explanation: It can be proved that it is impossible to make the two arrays equal.
Constraints:
n == nums1.length == nums2.length2 <= n <= 1050 <= nums1[i], nums2[j] <= 1090 <= k <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most efficient approach, which solves the problem in a single pass through the arrays. It simultaneously checks for impossibility conditions and calculates the required operations by keeping track of the total positive and negative differences needed.
Algorithm
- Handle the edge case where
k = 0. Ifnums1andnums2are not equal, return -1. Otherwise, return 0. - Initialize two
longvariables:pos_diff_sum = 0(to track total required increments) andneg_diff_sum = 0(to track total required decrements). - Single Pass: Iterate through the arrays from
i = 0ton-1.- Calculate the difference
diff = (long)nums2[i] - nums1[i]. - Check if
diffis divisible byk. If not, it's impossible, so return -1. - If
diff > 0, adddifftopos_diff_sum. This represents a deficit innums1[i]that needs to be filled by increments. - If
diff < 0, adddifftoneg_diff_sum. This represents a surplus innums1[i]that needs to be removed by decrements.
- Calculate the difference
- After the loop, check if the total deficits balance the total surpluses:
pos_diff_sum + neg_diff_sum != 0. If they don't balance, it's impossible to make the arrays equal. Return -1. - If they do balance, the total number of operations is the total amount of increments needed divided by
k. Returnpos_diff_sum / k.
Walkthrough
This approach is based on the key observation that the total amount of increments required must exactly balance the total amount of decrements. An operation (nums1[i] += k, nums1[j] -= k) essentially "transfers" a value of k from index j to index i.
We can iterate through the arrays once, calculating the difference diff = nums2[i] - nums1[i] at each index. We maintain two running sums:
pos_diff_sum: The sum of all positive differences. This represents the total value that needs to be added tonums1across all indices that require an increase.neg_diff_sum: The sum of all negative differences. This represents the total value that needs to be subtracted fromnums1across all indices that require a decrease.
During the iteration, we can immediately check if any diff is not divisible by k. After the loop, for a solution to be possible, the total increments must equal the total decrements, meaning pos_diff_sum must be equal to -neg_diff_sum, or pos_diff_sum + neg_diff_sum == 0. If this holds, the number of operations is simply pos_diff_sum / k, as each operation contributes k towards fulfilling the total positive difference.
class Solution { public long minOperations(int[] nums1, int[] nums2, int k) { int n = nums1.length; if (k == 0) { for (int i = 0; i < n; i++) { if (nums1[i] != nums2[i]) { return -1; } } return 0; } long pos_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's positive long neg_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's negative for (int i = 0; i < n; i++) { long diff = (long)nums2[i] - nums1[i]; if (diff % k != 0) { return -1; } if (diff > 0) { pos_diff_sum += diff; } else { neg_diff_sum += diff; } } if (pos_diff_sum + neg_diff_sum != 0) { return -1; } return pos_diff_sum / k; }}Complexity
Time
O(N), where N is the length of the arrays. We iterate through the arrays only once.
Space
O(1), as we only use a constant amount of extra space for our tracking variables.
Trade-offs
Pros
Highly efficient, solving the problem in a single pass.
Combines validation and calculation into one loop, reducing redundant work and improving performance.
Cons
The logic might be slightly less straightforward to grasp initially compared to the two-pass method as it combines checks and calculations.
Solutions
Solution
class Solution {public long minOperations(int[] nums1, int[] nums2, int k) { long ans = 0, x = 0; for (int i = 0; i < nums1.length; ++i) { int a = nums1[i], b = nums2[i]; if (k == 0) { if (a != b) { return -1; } continue; } if ((a - b) % k != 0) { return -1; } int y = (a - b) / k; ans += Math.abs(y); x += y; } return x == 0 ? ans / 2 : -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.