What is the minimum operations to make a uni-value grid problem about?

It requires making all elements equal by adding or subtracting a fixed integer x, combining array sorting and math logic.

How do I know if making a grid uni-value is possible?

Check that all elements have the same remainder when divided by x; differing remainders make it impossible.

Why is the median used to minimize operations?

Because adjusting all elements to the median minimizes the sum of absolute differences, which directly reduces the total steps needed.

What is the time complexity for this solution?

Flattening and sorting the grid takes O(mn log mn), and computing operations after that is O(mn).

Can this approach handle very large grids efficiently?

Yes, as it uses linear space and a single sort step, which is feasible for grids up to size 10^5 elements.

#2033

Medium

auto_awesome数组·数学

LeetCode 题解工作台

获取单值网格的最小操作数

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素加 x 或减 x 。单值网格是全部元素都相等的网格。返回使网格化为单值网格所需的最小操作数。如果不能，返回 -1 。示例 1：输入： grid = [[2,4],[6…

数组数学排序矩阵

题目描述

给你一个大小为 m x n 的二维整数网格 grid 和一个整数 x 。每一次操作，你可以对 grid 中的任一元素加 x 或减 x 。

单值网格 是全部元素都相等的网格。

返回使网格化为单值网格所需的最小操作数。如果不能，返回 -1 。

示例 1：

输入：grid = [[2,4],[6,8]], x = 2
输出：4
解释：可以执行下述操作使所有元素都等于 4 ： 
- 2 加 x 一次。
- 6 减 x 一次。
- 8 减 x 两次。
共计 4 次操作。

示例 2：

输入：grid = [[1,5],[2,3]], x = 1
输出：5
解释：可以使所有元素都等于 3 。

示例 3：

输入：grid = [[1,2],[3,4]], x = 2
输出：-1
解释：无法使所有元素相等。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= x, grid[i][j] <= 10⁴

lightbulb

解题思路

方法一：贪心

首先，要使得网格化为单值网格，那么网格的所有元素与 $x$ 的余数必须相同。

因此，我们可以先遍历网格，判断所有元素与 $x$ 的余数是否相同，若不同则返回 $-1$ 。否则，我们将所有元素放入数组中，对数组进行排序，取中位数，然后遍历数组，计算每个元素与中位数的差值，再除以 $x$ ，将所有的差值相加，即为答案。

时间复杂度 $O((m \times n) \times \log (m \times n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        nums = []
        mod = grid[0][0] % x
        for row in grid:
            for v in row:
                if v % x != mod:
                    return -1
                nums.append(v)
        nums.sort()
        mid = nums[len(nums) >> 1]
        return sum(abs(v - mid) // x for v in nums)

speed

复杂度分析

指标	值
时间	complexity is O(mn log mn) due to sorting the flattened grid. Space complexity is O(mn) for storing the flattened array. The arithmetic checks and operations scale linearly over the grid size after sorting.
空间	O(mn)

psychology

面试官常问的追问

外企场景

question_mark
Is every element reachable by adding or subtracting x?
question_mark
Can you explain why median minimizes total operations in this context?
question_mark
What happens if elements have different remainders modulo x?

warning

常见陷阱

外企场景

error
Forgetting to check modulo x feasibility before computing operations.
error
Choosing the wrong target value instead of the median.
error
Ignoring large grid constraints and assuming small input sizes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider minimizing operations when only additions are allowed.
arrow_right_alt
Handle grids where x can be negative, affecting operation directions.
arrow_right_alt
Compute minimal operations under additional constraints like limited moves per element.

help

常见问题

外企场景

继续练习

#1878 矩阵中最大的三个菱形和 #1030 距离顺序排列矩阵单元格 #1998 数组的最大公因数排序