LeetCode 2033 - Minimum Operations to Make a Uni-Value Grid

The problem gives us a 2D integer matrix called grid and an integer x. In one operation, we may either add x to a cell or subtract x from a cell. Our goal is to make every value in the grid equal using the minimum number of operations.

leetcodemediumarraymathsortingmatrix

LeetCode Problem 2033

Difficulty: 🟡 Medium
Topics: Array, Math, Sorting, Matrix

Solution

Problem Understanding

The problem gives us a 2D integer matrix called grid and an integer x. In one operation, we may either add x to a cell or subtract x from a cell. Our goal is to make every value in the grid equal using the minimum number of operations.

A key detail is that every operation changes a number by exactly x. We cannot increment or decrement by arbitrary values. For example, if x = 3, then a value can move from 1 to 4, 7, 10, and so on, but it can never become 2 or 5.

The output should be the minimum number of operations needed to transform the entire grid into a uni-value grid. If there is no way to make all numbers equal under these rules, we return -1.

The constraints are important:

  • The grid can contain up to 10^5 total elements.
  • Each value is at most 10^4.
  • A brute-force search over all possible target values for every cell combination would be far too slow.

This tells us we need a mathematically efficient solution.

An important observation is that two numbers can only be transformed into each other if their difference is divisible by x.

For example:

  • With x = 2, 2 can become 4, 6, 8, and so on.
  • But 2 can never become 3 because repeated additions or subtractions of 2 preserve parity.

Therefore, before doing anything else, we must verify that all numbers have the same remainder modulo x.

Some important edge cases include:

  • A grid with only one element, which already satisfies the condition.
  • Values that differ by amounts not divisible by x, making the answer immediately -1.
  • Large grids where efficiency matters.
  • Multiple valid target values, where we must choose the one minimizing total operations.

Approaches

Brute Force Approach

A straightforward idea is to try every possible target value and compute how many operations are needed to convert all cells into that target.

First, flatten the grid into a single array. Then, for every candidate target:

  1. Check whether every value can be converted into the target.
  2. Compute the number of operations required:

$$\frac{|value - target|}{x}$$ 3. Keep the minimum total.

This works because we directly evaluate every possible final value and choose the best one.

However, this approach becomes inefficient when the number of elements is large. If there are k elements and we try every element as a target, the complexity becomes O(k^2), which is too slow for k = 10^5.

Optimal Approach

The key insight comes from two mathematical observations.

First, feasibility:

All numbers must have the same remainder modulo x. Otherwise, it is impossible to transform them into a common value.

Second, minimizing operations:

Once we normalize the problem, each operation effectively moves a number by one step. The optimal target for minimizing total absolute distance is the median.

Suppose we divide all values by x conceptually. Then the problem becomes minimizing:

$$\sum |a_i - target|$$

This is a classic result: the median minimizes the sum of absolute deviations.

Therefore, the algorithm is:

  1. Flatten the grid.
  2. Check modulo consistency.
  3. Sort the array.
  4. Choose the median as the target.
  5. Sum the required operations.

This reduces the complexity to O(k log k) because sorting dominates the runtime.

Approach Time Complexity Space Complexity Notes
Brute Force O(k²) O(k) Tries every possible target value
Optimal O(k log k) O(k) Uses modulo feasibility check and median property

Here, k = m * n.

Algorithm Walkthrough

  1. Flatten the 2D grid into a 1D array.

Working with a single list simplifies sorting and iteration. Since the positions of elements do not matter, only their values matter. 2. Store the remainder of the first value modulo x.

Every other value must have the same remainder modulo x. If not, it is impossible to make all values equal. 3. Iterate through all values and verify modulo consistency.

For each value:

$$value \bmod x$$

must equal the remainder of the first element.

If any value fails this check, immediately return -1. 4. Sort the flattened array.

Sorting allows us to easily select the median value. 5. Select the median element as the target.

If there are k elements, the median index is:

$$k // 2$$

The median minimizes the total absolute distance. 6. Compute the total operations.

For every value:

$$operations += \frac{|value - median|}{x}$$

Since feasibility was already verified, the division will always be exact. 7. Return the total number of operations.

Why it works

The modulo condition guarantees that all numbers belong to the same transformation group under repeated additions or subtractions of x.

After normalization, each operation changes a value by exactly one unit. The problem then becomes minimizing the sum of absolute distances to a target value. The mathematical property of medians guarantees that the sum of absolute deviations is minimized at the median, so this strategy always produces the minimum number of operations.

Python Solution

from typing import List

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        values = []

        for row in grid:
            values.extend(row)

        remainder = values[0] % x

        for value in values:
            if value % x != remainder:
                return -1

        values.sort()

        median = values[len(values) // 2]

        operations = 0

        for value in values:
            operations += abs(value - median) // x

        return operations

The implementation begins by flattening the grid into a single list called values. This simplifies later processing because the relative positions of elements do not matter.

Next, the code stores the modulo remainder of the first value. Every other number must share this same remainder when divided by x. If any value differs, the function immediately returns -1 because no sequence of ±x operations can bridge the mismatch.

After validating feasibility, the array is sorted so that the median can be selected efficiently. The median element is chosen as the target value because it minimizes the sum of absolute distances.

Finally, the algorithm computes the total number of operations required to move every value to the median. Since each operation changes a value by exactly x, the number of operations is:

$$\frac{|value - median|}{x}$$

The accumulated total is returned as the final answer.

Go Solution

package main

import (
	"sort"
)

func minOperations(grid [][]int, x int) int {
	values := []int{}

	for _, row := range grid {
		values = append(values, row...)
	}

	remainder := values[0] % x

	for _, value := range values {
		if value%x != remainder {
			return -1
		}
	}

	sort.Ints(values)

	median := values[len(values)/2]

	operations := 0

	for _, value := range values {
		diff := value - median
		if diff < 0 {
			diff = -diff
		}

		operations += diff / x
	}

	return operations
}

The Go implementation follows the same logic as the Python solution. One small difference is that Go does not provide a built-in absolute value function for integers, so the code manually converts negative differences into positive ones.

The flattened array is built using slice appends, and sorting is handled using sort.Ints.

Because the constraints fit comfortably within standard integer ranges, regular int arithmetic is sufficient.

Worked Examples

Example 1

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

Step 1: Flatten the grid

values = [2, 4, 6, 8]

Step 2: Check modulo consistency

Value Value % 2
2 0
4 0
6 0
8 0

All remainders match, so the transformation is possible.

Step 3: Sort values

[2, 4, 6, 8]

Step 4: Choose median

median = values[4 // 2]
median = values[2]
median = 6

Using 4 would also produce the same minimum total because the array size is even.

Step 5: Compute operations

Value Distance to 6 Operations
2 4 2
4 2 1
6 0 0
8 2 1

Total:

2 + 1 + 0 + 1 = 4

Answer:

4

Example 2

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

Step 1: Flatten

values = [1, 5, 2, 3]

Step 2: Modulo check

Since x = 1, every number has remainder 0.

Transformation is possible.

Step 3: Sort

[1, 2, 3, 5]

Step 4: Choose median

median = 3

Step 5: Compute operations

Value Distance to 3 Operations
1 2 2
2 1 1
3 0 0
5 2 2

Total:

2 + 1 + 0 + 2 = 5

Answer:

5

Example 3

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

Step 1: Flatten

values = [1, 2, 3, 4]

Step 2: Modulo check

Value Value % 2
1 1
2 0

The remainders differ.

Therefore, it is impossible to make all values equal.

Answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(k log k) Sorting the flattened array dominates the runtime
Space O(k) The flattened array stores all grid elements

Here, k = m * n.

The modulo validation and operation counting each require linear time. The expensive step is sorting, which costs O(k log k). Since the problem allows up to 10^5 elements, this complexity is efficient enough.

Test Cases

from typing import List

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:
        values = []

        for row in grid:
            values.extend(row)

        remainder = values[0] % x

        for value in values:
            if value % x != remainder:
                return -1

        values.sort()

        median = values[len(values) // 2]

        operations = 0

        for value in values:
            operations += abs(value - median) // x

        return operations

sol = Solution()

assert sol.minOperations([[2, 4], [6, 8]], 2) == 4  # example 1
assert sol.minOperations([[1, 5], [2, 3]], 1) == 5  # example 2
assert sol.minOperations([[1, 2], [3, 4]], 2) == -1  # example 3

assert sol.minOperations([[5]], 3) == 0  # single element grid
assert sol.minOperations([[1, 3, 5]], 2) == 2  # already compatible values
assert sol.minOperations([[1, 4]], 2) == -1  # incompatible modulo values
assert sol.minOperations([[2, 2], [2, 2]], 5) == 0  # already uni-value
assert sol.minOperations([[1, 7], [13, 19]], 6) == 4  # larger jumps
assert sol.minOperations([[10000, 10000]], 1) == 0  # large identical values
assert sol.minOperations([[1, 1001]], 10) == 100  # large operation count
assert sol.minOperations([[1, 11, 21, 31]], 10) == 4  # median minimization
Test Why
[[2,4],[6,8]], x=2 Validates standard transformation case
[[1,5],[2,3]], x=1 Validates unrestricted movement
[[1,2],[3,4]], x=2 Validates impossible modulo mismatch
[[5]], x=3 Tests single-element edge case
[[1,3,5]], x=2 Tests compatible odd-number sequence
[[1,4]], x=2 Tests early impossibility detection
[[2,2],[2,2]], x=5 Tests already uni-value grid
[[1,7],[13,19]], x=6 Tests multiple large jumps
[[10000,10000]], x=1 Tests large equal values
[[1,1001]], x=10 Tests large operation accumulation
[[1,11,21,31]], x=10 Tests median-based optimization

Edge Cases

One important edge case is when the grid already contains identical values. In this situation, no operations are required, so the answer should be 0. A buggy implementation might still attempt unnecessary transformations or incorrectly compute distances. The current implementation handles this naturally because every distance to the median becomes zero.

Another critical edge case occurs when modulo values differ. For example, with x = 2, values 1 and 2 can never become equal because repeated additions or subtractions of 2 preserve parity. Without checking modulo consistency first, an implementation could incorrectly compute a numeric answer for an impossible scenario. The solution prevents this by validating all remainders before sorting.

A third important case is an even number of elements. In such situations, there are technically two middle values after sorting. Either median produces the same minimal total absolute deviation. Some implementations mistakenly try to average the two medians, but that can produce an invalid target that is unreachable under the operation rules. This implementation simply chooses one valid median directly from the array, guaranteeing correctness.