Minimum Operations to Make a Uni-Value Grid

What the problem is really asking

We have a grid, but the positions do not matter. In one operation we can move any value by exactly x, either up or down.

So the problem becomes:

• flatten the grid into one array
• check whether all values can ever meet
• choose the best final value
• count how many x-sized steps are needed

Key observation

Adding or subtracting x never changes a number's remainder modulo x.

That means two values can become equal only if they have the same remainder when divided by x.

For example, with x = 2, odd numbers always stay odd and even numbers always stay even. So [1, 2, 3, 4] can never become one value because the parities are mixed.

For this problem, every grid value must satisfy:

value % x == grid[0][0] % x

If even one value has a different remainder, the answer is -1.

Why the median is optimal

Once the remainder check passes, every value can reach every other value in x-sized steps.

Now we need to minimize the total distance to one final value. This is the classic median property:

For absolute distances, the median minimizes the total sum of distances.

If we pick a value too small, all large values pay extra moves. If we pick a value too large, all small values pay extra moves. The median balances those movements.

So after sorting the flattened array, the best target is:

values[values.length / 2]

Approach

1. Flatten the grid into an array.
2. While flattening, check that every number has the same value % x.
3. Sort the array.
4. Pick the median as the final common value.
5. Add abs(value - median) / x for every value.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minOperations(int[][] grid, int x) {
        List<Integer> values = new ArrayList<>();
        int remainder = grid[0][0] % x;

        for (int[] row : grid) {
            for (int value : row) {
                if (value % x != remainder) {
                    return -1;
                }
                values.add(value);
            }
        }

        Collections.sort(values);
        int target = values.get(values.size() / 2);
        int operations = 0;

        for (int value : values) {
            operations += Math.abs(value - target) / x;
        }

        return operations;
    }
}

Dry run

Take:

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

Flatten and sort:

[2, 4, 6, 8]

All values have remainder 0 modulo 2, so it is possible.

The median target is 6 if we choose the upper middle value:

• 2 -> 6 takes 2 operations
• 4 -> 6 takes 1 operation
• 6 -> 6 takes 0 operations
• 8 -> 6 takes 1 operation

Total operations:

2 + 1 + 0 + 1 = 4

Choosing 4 also gives 4 operations, because for an even number of elements either middle value is optimal.

Why not try every possible target?

You could test every grid value as a final target, but that would repeat the same distance calculation many times.

Sorting once and using the median gives the answer directly.

Common mistakes

1. Checking divisibility against the median too late

It works, but checking against grid[0][0] % x while flattening is simpler and can return -1 early.

2. Using the average instead of the median

The average minimizes squared distance, not absolute distance. Here each operation is linear distance divided by x, so the median is the right target.

3. Forgetting to divide by x

The distance tells us how much the value changes. The number of operations is how many x-sized jumps that distance contains.

Complexity

Let k = m * n, the total number of values in the grid.

Time Complexity: O(k log k)

Flattening takes O(k), sorting takes O(k log k), and counting operations takes O(k).

Space Complexity: O(k)

We store all grid values in a flattened array.