Minimum Operations to Make Array Equal II

Medium Arrays & Hashing Greedy Original on LeetCode

Minimum Operations to Make Array Equal II is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (count k-steps in one pass), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate the operations) up.

Problem

You are given two integer arrays nums1 and nums2 of equal length and an integer k. In one operation you choose two indices i and j and do nums1[i] += k and nums1[j] -= k together.

Return the minimum number of operations that turns nums1 into exactly nums2 (equal at every index), or -1 if that cannot be done.

Examples

Example 1

Input
nums1 = [5, 1, 8, 2], nums2 = [1, 5, 4, 6], k = 2
Output
4
Why
Indices 0 and 2 each sit 4 above their target (2 steps of k each), and indices 1 and 3 each sit 4 below. Pairing them up takes 4 operations.

Example 2

Input
nums1 = [3, 7], nums2 = [5, 4], k = 2
Output
-1
Why
Index 1 must drop by 3, which is not a multiple of k = 2, so it can never land exactly on 4.

Example 3

Input
nums1 = [4, 4, 4], nums2 = [4, 4, 4], k = 0
Output
0
Why
With k = 0 an operation changes nothing, but the arrays are already equal.

Constraints

  • n == nums1.length == nums2.length, 2 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 10^9
  • 0 <= k <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (simulate the operations)O(n · ops)O(n)
Optimal (count k-steps in one pass)O(n)O(1)

1Brute force (simulate the operations)

TimeO(n · ops)Every operation scans the array to find a surplus and a deficit index, and ops can be as large as (sum of differences) / k.
SpaceO(n)A working copy of nums1.

After checking that every difference is a multiple of k (and handling k = 0), keep applying the operation directly: pick an index that is still above its target and one that is still below, move each by k, and count. When one side runs out, the arrays are equal only if the other side ran out too.

  1. If k == 0, return 0 when the arrays are equal and -1 otherwise.
  2. If any nums1[i] - nums2[i] is not divisible by k, return -1.
  3. Repeat: find i with a[i] > nums2[i] and j with a[j] < nums2[j]; if either is missing, stop; else a[i] -= k, a[j] += k, ops++.
  4. Return ops if a equals nums2, otherwise -1.
class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        if (k == 0) return Arrays.equals(nums1, nums2) ? 0 : -1;
        for (int i = 0; i < n; i++)
            if ((nums1[i] - nums2[i]) % k != 0) return -1;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nums1[i];
        long ops = 0;
        while (true) {
            int up = -1, down = -1;
            for (int i = 0; i < n; i++) {
                if (up == -1 && a[i] > nums2[i]) up = i;
                if (down == -1 && a[i] < nums2[i]) down = i;
            }
            if (up == -1 || down == -1) break;
            a[up] -= k;
            a[down] += k;
            ops++;
        }
        for (int i = 0; i < n; i++) if (a[i] != nums2[i]) return -1;
        return ops;
    }
}

2Optimal (count k-steps in one pass)

TimeO(n)A single pass over the arrays.
SpaceO(1)Two 64-bit counters.

Each index needs |nums1[i] - nums2[i]| / k steps of size k, downward if it is too large and upward if it is too small, and that is only possible when the difference is a multiple of k. Every operation supplies exactly one downward and one upward step, so the totals of both kinds must be equal, and that total is the minimum number of operations. k = 0 is special: nothing can change.

  1. If k == 0, return 0 if the arrays are equal, else -1.
  2. down = up = 0. For each i, d = nums1[i] - nums2[i]; if d % k != 0 return -1.
  3. If d > 0, down += d / k; else up += -d / k.
  4. Return down if down == up, else -1.
class Solution {
    public long minOperations(int[] nums1, int[] nums2, int k) {
        if (k == 0) return Arrays.equals(nums1, nums2) ? 0 : -1;
        long down = 0, up = 0;
        for (int i = 0; i < nums1.length; i++) {
            long d = (long) nums1[i] - nums2[i];
            if (d % k != 0) return -1;
            if (d > 0) down += d / k;
            else up += -d / k;
        }
        return down == up ? down : -1;
    }
}

Edge cases to test

  • k = 0: the answer is 0 if the arrays are already equal, otherwise -1
  • A difference that is not a multiple of k: -1
  • Total surplus and total deficit do not match: -1
  • Arrays already equal: 0
  • Large values with k = 1, where the answer needs 64 bits

Hints

Hint 1

Look at each index on its own: how much does nums1[i] have to move, and in which direction?

Hint 2

Each index must move by a multiple of k, and every operation performs exactly one k-step down and one k-step up.

Hint 3

So count k-steps down and k-steps up separately. They must be equal, and that common count is the answer.

FAQ

What is the best time complexity for Minimum Operations to Make Array Equal II?

Optimal (count k-steps in one pass) runs in O(n) time and O(1) extra space. A single pass over the arrays.

Which pattern does Minimum Operations to Make Array Equal II use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Minimum Operations to Make Array Equal II?

Yes. Brute force (simulate the operations) takes O(n · ops) time and O(n) space. After checking that every difference is a multiple of k (and handling k = 0), keep applying the operation directly: pick an index that is still above its target and one that is still below, move each by k, and count.

Which edge cases should I test for Minimum Operations to Make Array Equal II?

k = 0: the answer is 0 if the arrays are already equal, otherwise -1; A difference that is not a multiple of k: -1; Total surplus and total deficit do not match: -1; Arrays already equal: 0; Large values with k = 1, where the answer needs 64 bits.