NeetCode #927LC-2033MediumMath & Geometry
← Back to All Problems#927 · #2033 · Minimum Operations to Make a Uni-Value Grid(获取单值网格的最小操作数)
📌 Problem Statement & Constraints
Given an
m x n integer matrix grid and an integer x, one operation adds or subtracts x from any single element. Return the minimum number of operations to make all elements equal, or -1 if impossible. Constraints: 1 <= m, n <= 10^5, 1 <= m * n <= 10^5, 1 <= x, grid[i][j] <= 10^4.💡 Core Algorithmic Approaches
- Feasibility: every value must share the same remainder modulo
x; otherwise no sequence of+x/-xsteps can ever make them equal, so return -1. - Write each value as
r + k * x; the problem reduces to making all thekequal while minimising the number of unit steps. - The classic result is that the sum of absolute deviations is minimised at the median, so sort the values and target
flat[len // 2]. - The answer is
sum(abs(v - median) // x); every term is exact because all values are congruent modulox.
💻 Benchmark Python3 Implementation
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
flat = [v for row in grid for v in row]
r = flat[0] % x
for v in flat:
if v % x != r: # different residues -> impossible
return -1
flat.sort()
median = flat[len(flat) // 2]
return sum(abs(v - median) // x for v in flat)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n log(m * n)): the sort dominates.
💾 Space Complexity
O(m * n): the flattened array.
⚠️ Interview Pitfalls & Follow-ups
- Targeting the mean instead of the median: the mean does not minimise the sum of absolute deviations and may not even be reachable by
xsteps. - Omitting the residue check: with mixed residues the arithmetic still produces a number, but the correct answer is -1.
- Worrying about which median for even lengths: either middle index gives the same optimal sum, so
len // 2is fine. - Multiplying the element count by the step size: each move shifts a value by exactly
x, so the count isabs(v - median) // x, not the raw deviation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.