⚡Flashcard Drill➔
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

  1. Feasibility: every value must share the same remainder modulo x; otherwise no sequence of +x/-x steps can ever make them equal, so return -1.
  2. Write each value as r + k * x; the problem reduces to making all the k equal while minimising the number of unit steps.
  3. The classic result is that the sum of absolute deviations is minimised at the median, so sort the values and target flat[len // 2].
  4. The answer is sum(abs(v - median) // x); every term is exact because all values are congruent modulo x.

💻 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 x steps.
  • 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 // 2 is fine.
  • Multiplying the element count by the step size: each move shifts a value by exactly x, so the count is abs(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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems