Minimum Operations to Make Array Equal II

MEDIUM

Description

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.
1^st operation: i = 2, j = 0. After applying the operation, nums1 = [1,3,4,4].
2^nd 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

Checkout 2 different approaches to solve Minimum Operations to Make Array Equal II. Click on different approaches to view the approach and algorithm in detail.

Single-Pass Optimal Approach

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.

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.

class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        if (k == 0) {
            for (int i = 0; i < n; i++) {
                if (nums1[i] != nums2[i]) {
                    return -1;
                }
            }
            return 0;
        }

        long pos_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's positive
        long neg_diff_sum = 0; // Sum of (nums2[i] - nums1[i]) where it's negative

        for (int i = 0; i < n; i++) {
            long diff = (long)nums2[i] - nums1[i];

            if (diff % k != 0) {
                return -1;
            }

            if (diff > 0) {
                pos_diff_sum += diff;
            } else {
                neg_diff_sum += diff;
            }
        }

        if (pos_diff_sum + neg_diff_sum != 0) {
            return -1;
        }

        return pos_diff_sum / k;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the arrays. We iterate through the arrays only once.Space Complexity: O(1), as we only use a constant amount of extra space for our tracking variables.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Operations to Make Array Equal II. Click on different languages to view the code.

class Solution {
public
  long minOperations(int[] nums1, int[] nums2, int k) {
    long ans = 0, x = 0;
    for (int i = 0; i < nums1.length; ++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 += Math.abs(y);
      x += y;
    }
    return x == 0 ? ans / 2 : -1;
  }
}

Video Solution

Watch the video walkthrough for Minimum Operations to Make Array Equal II

Patterns:

MathGreedy

Data Structures:

Array

Companies:

Walmart Labs |