Minimum Operations to Make Array Equal II

Med

#2321Time: 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.1 company

Patterns

Math Greedy

Data structures

Array

Companies

Walmart Labs

Prompt

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 <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁹
0 <= k <= 10⁵

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. If nums1 and nums2 are not equal, return -1. Otherwise, return 0.
Initialize two long variables: pos_diff_sum = 0 (to track total required increments) and neg_diff_sum = 0 (to track total required decrements).
Single Pass: Iterate through the arrays from i = 0 to n-1.
- Calculate the difference diff = (long)nums2[i] - nums1[i].
- Check if diff is divisible by k. If not, it's impossible, so return -1.
- If diff > 0, add diff to pos_diff_sum. This represents a deficit in nums1[i] that needs to be filled by increments.
- If diff < 0, add diff to neg_diff_sum. This represents a surplus in nums1[i] that needs to be removed by decrements.
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. Return pos_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 to nums1 across 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 from nums1 across 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.

1class Solution {2    public long minOperations(int[] nums1, int[] nums2, int k) {3        int n = nums1.length;4        if (k == 0) {5            for (int i = 0; i < n; i++) {6                if (nums1[i] != nums2[i]) {7                    return -1;8                }9            }10            return 0;11        }12 13        long pos_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's positive14        long neg_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's negative15 16        for (int i = 0; i < n; i++) {17            long diff = (long)nums2[i] - nums1[i];18 19            if (diff % k != 0) {20                return -1;21            }22 23            if (diff > 0) {24                pos_diff_sum += diff;25            } else {26                neg_diff_sum += diff;27            }28        }29 30        if (pos_diff_sum + neg_diff_sum != 0) {31            return -1;32        }33 34        return pos_diff_sum / k;35    }36}

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.

This approach involves iterating through the arrays twice. The first pass validates if a solution is possible by checking two conditions: the element-wise differences must be divisible by k, and the total sum of both arrays must be equal. The second pass calculates the total number of required operations.

Algorithm

Handle the edge case where k = 0. If nums1 and nums2 are not equal, return -1. Otherwise, return 0.
First Pass: Iterate through the arrays to check for impossibility.
- Initialize long variables sum1 = 0 and sum2 = 0.
- For each index i from 0 to n-1:
  - Add nums1[i] to sum1 and nums2[i] to sum2.
  - Check if the absolute difference |nums1[i] - nums2[i]| is not divisible by k. If it's not, a solution is impossible, so return -1.
After the first pass, check if sum1 is not equal to sum2. If the total sums differ, it's impossible to make the arrays equal, so return -1.
Second Pass: If all checks have passed, a solution is guaranteed to exist. Iterate through the arrays again to count the operations.
- Initialize a long counter operations = 0.
- For each index i, if nums1[i] < nums2[i], it means nums1[i] needs to be incremented. The number of increments of k needed is (nums2[i] - nums1[i]) / k. Add this value to operations.
Return the final operations count.

Walkthrough

The core idea is to first ensure that a transformation is possible before calculating the minimum operations. This separation of concerns can make the logic easier to follow.

Impossibility Conditions:

k = 0: If k is 0, the operation nums1[i] += 0 and nums1[j] -= 0 does not change the array. Therefore, nums1 can only be made equal to nums2 if they are already identical. If nums1[i] != nums2[i] for any i, it's impossible.
Divisibility: For k > 0, each change to an element nums1[i] is a multiple of k. Therefore, the difference nums2[i] - nums1[i] must be divisible by k for all i. If not, it's impossible to match nums1[i] to nums2[i].
Sum Equality: Each operation increases one element by k and decreases another by k, leaving the total sum of nums1 unchanged. Thus, a necessary condition is that the sum of elements in nums1 must equal the sum of elements in nums2.

Calculation:

If all conditions for possibility are met, we can calculate the operations. The total number of operations is determined by the total amount of increments needed. Since the total increments must balance the total decrements (due to sum equality), we only need to count one side. We can sum up all the required +k increments and that gives us the answer.

1class Solution {2    public long minOperations(int[] nums1, int[] nums2, int k) {3        int n = nums1.length;4        if (k == 0) {5            for (int i = 0; i < n; i++) {6                if (nums1[i] != nums2[i]) {7                    return -1;8                }9            }10            return 0;11        }12 13        long sum1 = 0;14        long sum2 = 0;15 16        // First Pass: Check for impossibility17        for (int i = 0; i < n; i++) {18            if (Math.abs((long)nums1[i] - nums2[i]) % k != 0) {19                return -1;20            }21            sum1 += nums1[i];22            sum2 += nums2[i];23        }24 25        if (sum1 != sum2) {26            return -1;27        }28 29        // Second Pass: Calculate operations30        long operations = 0;31        for (int i = 0; i < n; i++) {32            if (nums1[i] < nums2[i]) {33                operations += ((long)nums2[i] - nums1[i]) / k;34            }35        }36 37        return operations;38    }39}

Complexity

Time

O(N), where N is the length of the arrays. We perform two separate linear scans of the arrays.

Space

O(1), as we only use a few variables to store sums and the operation count, regardless of the input size.

Trade-offs

Pros

Conceptually simple and easy to understand.
Separates the validation logic from the calculation logic, which can improve readability.

Cons

Less efficient as it requires iterating through the input arrays twice, performing more operations than necessary.

Solutions

Solution

1class Solution {2public3  long minOperations(int[] nums1, int[] nums2, int k) {4    long ans = 0, x = 0;5    for (int i = 0; i < nums1.length; ++i) {6      int a = nums1[i], b = nums2[i];7      if (k == 0) {8        if (a != b) {9          return -1;10        }11        continue;12      }13      if ((a - b) % k != 0) {14        return -1;15      }16      int y = (a - b) / k;17      ans += Math.abs(y);18      x += y;19    }20    return x == 0 ? ans / 2 : -1;21  }22}

1class 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 ; } };

1class Solution : def minOperations ( self , nums1 : List [ int ], nums2 : List [ int ], k : int ) -> int : ans = x = 0 for a , b in zip ( nums1 , nums2 ): if k == 0 : if a != b : return - 1 continue if ( a - b ) % k : return - 1 y = ( a - b ) // k ans += abs ( y ) x += y return - 1 if x else ans // 2

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.

← Previous

Previous problem

Next problem