Skip to main content
Talentd

Minimum Operations to Make Array Equal II - Solution & Explanation

MediumArrayMathGreedy13 min readAsked at: Walmart Labs
Practice this problem

Problem Statement

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 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.length
  • 2 <= n <= 105
  • 0 <= nums1[i], nums2[j] <= 109
  • 0 <= 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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Balance Differences Approach

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.

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Leetcode 2541: Minimum Operations to Make Array Equal II (Biweekly Contest 96) • Algorithms Casts • 810 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Operations to Make Array Equal II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Operations to Make Arrays Similar

Next

Minimum Operations to Make Array Equal