#2033

Medium

LeetCode Problem Workspace

Minimum Operations to Make a Uni-Value Grid

Determine the fewest additions or subtractions of x to make all grid elements identical using array and math logic.

Problem Statement

Given a 2D integer grid of size m x n and an integer x, you can perform operations by adding or subtracting x from any grid element. Determine the minimal number of operations required to make all elements equal.

If it is impossible to reach a uni-value grid because elements have different remainders modulo x, return -1. Your task is to implement a function that computes this minimum operation count efficiently for any grid configuration.

Examples

Example 1

Input: grid = [[2,4],[6,8]], x = 2

Output: 4

We can make every element equal to 4 by doing the following:

Add x to 2 once.
Subtract x from 6 once.
Subtract x from 8 twice. A total of 4 operations were used.

Example 2

Input: grid = [[1,5],[2,3]], x = 1

Output: 5

We can make every element equal to 3.

Example 3

Input: grid = [[1,2],[3,4]], x = 2

Output: -1

It is impossible to make every element equal.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
1 <= x, grid[i][j] <= 104

Solution Approach

Flatten and Sort the Grid

Convert the 2D grid into a 1D array to simplify operations. Sorting helps identify the median, which minimizes total distance when adjusting elements by multiples of x.

Check Feasibility Using Remainders

For the operation to succeed, all elements must have the same remainder when divided by x. If any element differs, return -1 immediately since no sequence of additions or subtractions will unify the grid.

Compute Operations via Median

Once feasible, pick the median value of the sorted array as the target. Calculate the number of x-sized steps needed for each element to reach the median, summing these steps to get the minimal total operations.

Complexity Analysis

Metric	Value
Time	O(mn \times \log{mn})
Space	O(mn)

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy

Firstly, to make the grid a single-value grid, the remainder of all elements of the grid with $x$ must be the same.

1

2

3

4

5

6

7

8

9

10

11

12

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)

Continue Practicing

#1878 get biggest three rhombus sums in a grid #1030 matrix cells in distance order #1998 gcd sort of an array