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.

#2541

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

使数组中所有元素相等的最小操作数 II

给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：选择两个下标 i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之， nums1[i] = nums1[i] + k 且 num…

数组数学贪心

题目描述

给你两个整数数组 nums1 和 nums2 ，两个数组长度都是 n ，再给你一个整数 k 。你可以对数组 nums1 进行以下操作：

选择两个下标 i 和 j ，将 nums1[i] 增加 k ，将 nums1[j] 减少 k 。换言之，nums1[i] = nums1[i] + k 且 nums1[j] = nums1[j] - k 。

如果对于所有满足 0 <= i < n 都有 num1[i] == nums2[i] ，那么我们称 nums1 等于 nums2 。

请你返回使 nums1 等于 nums2 的最少操作数。如果没办法让它们相等，请你返回 -1 。

示例 1：

输入：nums1 = [4,3,1,4], nums2 = [1,3,7,1], k = 3
输出：2
解释：我们可以通过 2 个操作将 nums1 变成 nums2 。
第 1 个操作：i = 2 ，j = 0 。操作后得到 nums1 = [1,3,4,4] 。
第 2 个操作：i = 2 ，j = 3 。操作后得到 nums1 = [1,3,7,1] 。
无法用更少操作使两个数组相等。

示例 2：

输入：nums1 = [3,8,5,2], nums2 = [2,4,1,6], k = 1
输出：-1
解释：无法使两个数组相等。

提示：

n == nums1.length == nums2.length
2 <= n <= 10⁵
0 <= nums1[i], nums2[j] <= 10⁹
0 <= k <= 10⁵

lightbulb

解题思路

方法一：一次遍历

我们用变量 $x$ 记录加减次数的差值，用变量 $ans$ 记录操作次数。

遍历数组，对于每个位置 $i$ ，如果存在 $k=0$ 并且 $a_i \neq b_i$ ，则无法使两个数组相等，返回 $-1$ 。否则，如果 $k \neq 0$ ，则 $a_i - b_i$ 必须是 $k$ 的倍数，否则无法使两个数组相等，返回 $-1$ 。接下来，我们更新 $x$ 和 $ans$ 。

最后，如果 $x \neq 0$ ，则无法使两个数组相等，返回 $-1$ 。否则，返回 $\frac{ans}{2}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2598 执行操作后的最大 MEX #2601 质数减法运算 #2607 使子数组元素和相等