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:
i and j and increment nums1[i] by k and decrement nums1[j] by k. In other words, nums1[i] = nums1[i] + k and nums1[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 <= 105Problem Overview: You are given two arrays nums1 and nums2 and an integer k. One operation adds k to one index of nums1 and subtracts k from another index. The task is to compute the minimum number of operations required to transform nums1 into nums2, or return -1 if it cannot be done.
Approach 1: Brute Force Redistribution (Simulation) (Time: O(n^2), Space: O(1))
Compute the difference array diff[i] = nums1[i] - nums2[i]. Positive values mean the index has extra value that must be distributed elsewhere, while negative values mean it needs value. A naive simulation repeatedly transfers k from indices with positive difference to indices with negative difference until all differences reach zero. Each transfer reduces one positive and one negative bucket by k. This approach works conceptually but requires nested scans to find matching indices, leading to O(n^2) time in the worst case.
Approach 2: Balance Differences (Greedy + Math) (Time: O(n), Space: O(1))
The key observation: every operation moves exactly k units from one index to another. Compute diff = nums1[i] - nums2[i] for each index. If k == 0, the arrays must already be identical because operations change nothing. Otherwise, each difference must be divisible by k; if diff % k != 0, transformation is impossible.
Split the differences into two groups. If diff > 0, that index has surplus and contributes diff / k transferable units. If diff < 0, it requires -diff / k units. Since every operation transfers exactly one unit (k) from a surplus index to a deficit index, the total surplus units must equal the total deficit units. The minimum operations equal the total surplus units. This single pass solution uses simple arithmetic and greedy balancing over the array, combining ideas from math constraints and greedy balancing.
Recommended for interviews: The balance differences approach is the expected solution. Interviewers want you to recognize that each operation conserves total sum and transfers exactly k. The brute force explanation demonstrates understanding of redistribution, but the O(n) greedy math solution shows the key insight about divisibility and balancing positive and negative differences.
In this approach, we need to balance the differences between the corresponding elements in nums1 and nums2. For each index i, calculate the difference: diff[i] = nums2[i] - nums1[i]. For all positive differences, attempt to cancel them out with corresponding negative differences by incrementing one and decrementing the other by the value of k. If the differences aren't balanced, it's impossible to make the arrays equal.
The function iterates over each pair of corresponding elements in nums1 and nums2 to compute the total number of positive and negative differences required to achieve equality. If the positive and negative required increments match, it returns the number of operations, otherwise -1.
Time Complexity: O(n), where n is the length of the arrays.
Space Complexity: O(1), as only a constant amount of extra space is needed.
We use a variable x to record the difference in the number of additions and subtractions, and a variable ans to record the number of operations.
We traverse the array, and for each position i, if k=0 and a_i neq b_i, then it is impossible to make the two arrays equal, so we return -1. Otherwise, if k neq 0, then a_i - b_i must be a multiple of k, otherwise it is impossible to make the two arrays equal, so we return -1. Next, we update x and ans.
Finally, if x neq 0, then it is impossible to make the two arrays equal, so we return -1. Otherwise, we return \frac{ans}{2}.
The time complexity is O(n), and the space complexity is O(1), where n is the length of the array.
| Approach | Complexity |
|---|---|
| Balance Differences Approach | Time Complexity: O(n), where n is the length of the arrays. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Redistribution (Simulation) | O(n^2) | O(1) | Conceptual understanding of how values move between indices |
| Balance Differences (Greedy + Math) | O(n) | O(1) | Optimal solution for interviews and large arrays |
Minimum Operations to Make Array Equal II || leetcode Biweekly 96 || Leetcode Medium • BinaryMagic • 1,329 views views
Watch 9 more video solutions →Practice Minimum Operations to Make Array Equal II with our built-in code editor and test cases.
Practice on FleetCode