#2541

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Operations to Make Array Equal II

Calculate the minimum operations to make two integer arrays equal using greedy adjustments with modular checks efficiently.

array math greedy

Problem Statement

You are given two integer arrays nums1 and nums2 of the same length n, along with an integer k. You can perform operations that increase one element in nums1 by k while decreasing another by k in a single move.

The goal is to make nums1 exactly equal to nums2 at all indices. Return the minimum number of operations needed. If it is impossible to equalize the arrays due to modular incompatibility or imbalance, return -1.

Examples

Example 1

Input: nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3

Output: 2

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

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

Solution Approach

Compute Differences and Check Modulo

For each index, calculate the difference nums1[i] - nums2[i]. If the difference modulo k is not zero, it is impossible to balance, so return -1 immediately. This ensures the greedy operation is feasible.

Balance Surplus and Deficit

Sum the positive differences as surplus and negative differences as deficit. The greedy choice is to apply operations that reduce surplus while increasing deficit until both reach zero. The total operations are the sum of absolute differences divided by k.

Return Result

If after processing all elements, the surplus equals the deficit in absolute value, return the total operations. Otherwise, return -1. This step validates the invariant that operations maintain overall balance.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is processed once for difference and balancing checks. Space complexity is O(1) beyond input storage since only counters for surplus, deficit, and operations are maintained.

What Interviewers Usually Probe

Ask about cases where differences cannot be reconciled due to modulo k incompatibility.
Check whether the candidate correctly computes total operations by summing divided differences.
Listen for explanation of greedy balancing between surplus and deficit elements.

Common Pitfalls or Variants

Common pitfalls

Ignoring the modulo k check before attempting operations leads to incorrect results.
Summing positive and negative differences without considering k may produce fractional operations.
Failing to verify that total surplus equals total deficit can return impossible counts.

Follow-up variants

Change the operation to allow multiple indices simultaneously and analyze minimal total moves.
Restrict k to 1 and study performance on very large arrays, focusing on greedy correctness.
Allow nums1 and nums2 to contain negative numbers and observe modular arithmetic adjustments.

FAQ

What is the main pattern used in Minimum Operations to Make Array Equal II?

The problem follows a greedy choice plus invariant validation pattern, focusing on balancing surplus and deficit differences modulo k.

Why do we check differences modulo k?

Checking modulo k ensures each difference can be resolved with integer operations; if any difference is not divisible by k, the arrays cannot be equalized.

How do we calculate the minimal number of operations?

Sum all positive differences and divide by k; this represents the least operations needed to transfer surplus to deficits efficiently.

Can this approach handle large arrays efficiently?

Yes, because it only requires a single pass over the arrays to compute differences and sum operations, giving O(n) time complexity.

What common mistakes should I avoid?

Common mistakes include skipping modulo checks, not balancing surplus with deficit correctly, and miscounting operations when differences are not aligned with k.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class 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

Continue Practicing

#2598 smallest missing non negative integer after operations #2601 prime subtraction operation #2607 make k subarray sums equal