Watch 10 video solutions for Minimum Operations to Make Array Equal II, a medium level problem involving Array, Math, Greedy. This walkthrough by BinaryMagic has 1,329 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |