Minimum Operations to Make Array Equal II solution and explanation
6 more videos on this problem
Leetcode 2541: Minimum Operations to Make Array Equal II (Biweekly Contest 96)Algorithms Casts · 15:18 · 810 views
2541. Minimum Operations to Make Array Equal II (Leetcode Medium)Programming Live with Larry · 8:49 · 453 views
2541. Minimum Operations to Make Array Equal II | Leetcode BiWeekly contest 96Tech Courses · 8:17 · 442 views
2541. Minimum Operations to Make Array Equal II || LeetCode Bi-Weekly Contest 96 || MediumAmit Maity · 7:45 · 218 views
Leetcode 6275. || Minimum Operations to Make Array Equal II || Leetcode Biweekly Medium || cppKomal Pal · 11:13 · 134 views
LeetCode (Biweekly Contest) | Minimum Operations to Make Array Equal II | Explanation & CodeDivyam Kakkar - LevelUp Coding · 13:29 · 53 views
LeetCode 2541 | Minimum Operation to Make Array Equal IIMathematics · 36:27 · 46 views
The problem
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
Approach overview
Problem 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 1: Balance Differences Approach
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.
def minOperations(nums1, nums2, k):
if k == 0:
return -1 if nums1 != nums2 else 0
pos_diff = 0
neg_diff = 0
for x, y in zip(nums1, nums2):
diff = y - x
if diff % k != 0:
return -1
if diff > 0:
pos_diff += diff // k
else:
neg_diff -= diff // k
return pos_diff if pos_diff == neg_diff else -1public int minOperations(int[] nums1, int[] nums2, int k) {
if (k == 0) {
for (int i = 0; i < nums1.length; i++) {
if (nums1[i] != nums2[i]) return -1;
}
return 0;
}
long pos_diff = 0, neg_diff = 0;
for (int i = 0; i < nums1.length; i++) {
long diff = nums2[i] - nums1[i];
if (diff % k != 0) return -1;
if (diff > 0) pos_diff += diff / k;
else neg_diff -= diff / k;
}
return pos_diff == neg_diff ? (int) pos_diff : -1;
}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.
Approach 2: Single Pass
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.
class Solution {
public:
long long minOperations(vector<int>& nums1, vector<int>& nums2, int k) {
long long ans = 0, x = 0;
for (int i = 0; i < nums1.size(); ++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 += abs(y);
x += y;
}
return x == 0 ? ans / 2 : -1;
}
};function minOperations(nums1: number[], nums2: number[], k: number): number {
const n = nums1.length;
if (k === 0) {
return nums1.every((v, i) => v === nums2[i]) ? 0 : -1;
}
let sum1 = 0;
let sum2 = 0;
for (let i = 0; i < n; i++) {
const diff = nums1[i] - nums2[i];
sum1 += diff;
if (diff % k !== 0) {
return -1;
}
sum2 += Math.abs(diff);
}
if (sum1 !== 0) {
return -1;
}
return sum2 / (k * 2);
}long long minOperations(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
if (k == 0) {
for (int i = 0; i < nums1Size; i++) {
if (nums1[i] != nums2[i]) {
return -1;
}
}
return 0;
}
long long sum1 = 0;
long long sum2 = 0;
for (int i = 0; i < nums1Size; i++) {
long long diff = nums1[i] - nums2[i];
sum1 += diff;
if (diff % k != 0) {
return -1;
}
sum2 += llabs(diff);
}
if (sum1 != 0) {
return -1;
}
return sum2 / (k * 2);
}func minOperations(nums1 []int, nums2 []int, k int) int64 {
ans, x := 0, 0
for i, a := range nums1 {
b := nums2[i]
if k == 0 {
if a != b {
return -1
}
continue
}
if (a-b)%k != 0 {
return -1
}
y := (a - b) / k
ans += abs(y)
x += y
}
if x != 0 {
return -1
}
return int64(ans / 2)
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn min_operations(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
let k = k as i64;
let n = nums1.len();
if k == 0 {
return if nums1.iter().enumerate().all(|(i, &v)| v == nums2[i]) {
0
} else {
-1
};
}
let mut sum1 = 0;
let mut sum2 = 0;
for i in 0..n {
let diff = (nums1[i] - nums2[i]) as i64;
sum1 += diff;
if diff % k != 0 {
return -1;
}
sum2 += diff.abs();
}
if sum1 != 0 {
return -1;
}
sum2 / (k * 2)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Balance Differences Approach | Time Complexity: O(n), where n is the length of the arrays. |
| Single Pass | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Operations to Make Array Equal II easy or hard?
Minimum Operations to Make Array Equal II is rated Medium difficulty. The challenge is recognizing that each operation transfers exactly k between indices and that differences must be divisible by k. Once that observation is made, the final solution is a straightforward O(n) pass.
Minimum Operations to Make Array Equal II Python/Java solution
Both Python and Java implementations follow the same logic: iterate through the arrays, check diff % k, and maintain counters for positive and negative units. Return the positive unit total if it equals the negative total, otherwise return -1. The implementation runs in O(n) time and constant space.
How to solve Minimum Operations to Make Array Equal II in O(n)?
Iterate through the arrays and compute diff = nums1[i] - nums2[i]. If k > 0 and diff is not divisible by k, the transformation is impossible. Accumulate positive diff/k values as surplus units and negative diff/k values as required units. If total surplus equals total deficit, that value gives the minimum number of operations.
What is the best approach for Minimum Operations to Make Array Equal II?
The balance differences greedy approach is the optimal solution. Compute nums1[i] - nums2[i] for every index and ensure each difference is divisible by k. Sum the positive differences divided by k and match them with negative ones. If both totals are equal, that value is the minimum operations. The algorithm runs in O(n) time with O(1) space.
Is Minimum Operations to Make Array Equal II asked at Google/Amazon/Meta?
Problems combining array manipulation with greedy balancing and arithmetic constraints frequently appear in interviews at large companies such as Amazon, Google, and Meta. Variants often test reasoning about conservation of value, difference arrays, and validating transformation feasibility.
What data structure is used in Minimum Operations to Make Array Equal II?
The solution mainly uses simple array traversal and arithmetic counters. No complex data structures are required. The logic relies on computing a difference per index and balancing positive and negative contributions using integer math.
What is the time complexity of Minimum Operations to Make Array Equal II?
The optimal solution runs in O(n) time because it scans the arrays once to compute and balance differences. Space complexity is O(1) since only a few counters are maintained. A naive simulation approach can degrade to O(n^2) if you repeatedly search for indices to transfer values.