371. Minimum Operations to Make a Uni-Value Grid

An element a can reach a target t only if (a - t) is divisible by x. If so, |a - t| / x operations are required. Try every grid value as the target and take the minimum.

Approach

1. Flatten the grid into flat. If any two values have different remainders modulo x, return -1.
2. For each candidate t in flat, compute sum(|a - t| / x for a in flat).
3. Return the minimum.

Complexity

• Time: O((m·n)²).
• Space: O(m·n) for the flat copy.

import java.util.*;

class Solution {
    public int minOperations(int[][] grid, int x) {
        List<Integer> flat = new ArrayList<>();
        for (int[] row : grid) {
            for (int v : row) {
                flat.add(v);
            }
        }
        int base = flat.get(0) % x;
        for (int v : flat) {
            if (v % x != base) return -1;
        }
        int best = Integer.MAX_VALUE;
        for (int t : flat) {
            int ops = 0;
            for (int a : flat) {
                ops += Math.abs(a - t) / x;
            }
            best = Math.min(best, ops);
        }
        return best;
    }
}

After a quick feasibility check, the problem reduces to a classic question: pick a target value t that minimises Σ |a - t|. That sum is minimised at the median — there's a clean exchange argument for why.

Step 1 — Feasibility

Each operation adds or subtracts x from a single cell, so a cell's value mod x never changes. To make every cell equal to some target t, every cell must already have the same remainder t mod x. So:

1. Pick any cell — say flat[0]. Let base = flat[0] % x.
2. If any other cell has a different remainder mod x, the answer is -1 (impossible).

Step 2 — Counting operations

Once feasibility is confirmed, the number of operations to turn cell value a into target t is exactly |a - t| / x. Total operations:

total(t) = (1 / x) · Σ |a - t|

So minimising total(t) is the same as minimising Σ |a - t| — a classic 1D problem.

Step 3 — Median is the optimum

Claim: for any collection of numbers a_1 ≤ a_2 ≤ … ≤ a_m, the value of t that minimises Σ |a_i - t| is any median of the collection.

Why (exchange argument): suppose t is currently to the left of the median. Pick a small step ε > 0 and consider t' = t + ε. Each term |a_i - t| changes by:

• +ε if a_i < t (we moved away from a_i),
• -ε if a_i > t (we moved toward a_i),
• something between if a_i is right at t.

Since fewer than half of the a_i's are below t (otherwise t would already be at the median), more terms decrease than increase, so total(t') is smaller. So we keep moving right until we hit the median. A symmetric argument shows we shouldn't go past it.

Steps

1. Flatten the grid into flat.
2. Feasibility: if any(v % x != flat[0] % x for v in flat), return -1.
3. Sort flat.
4. Pick target = flat[len(flat) // 2] (lower median when count is even — both medians give the same answer for this sum).
5. Return sum(abs(a - target) for a in flat) // x.

Walk-through 1: grid = [[2,4],[6,8]], x = 2

Flatten: [2, 4, 6, 8]. Remainders mod 2: all 0. Feasible.

Sort: [2, 4, 6, 8]. Median (lower of two middles): flat[2] = 6.

Sum of |a - 6|: |2-6| + |4-6| + |6-6| + |8-6| = 4 + 2 + 0 + 2 = 8.

Operations: 8 / 2 = 4. ✓

Walk-through 2: grid = [[1,2],[3,4]], x = 2

Flatten: [1, 2, 3, 4]. Remainders: [1, 0, 1, 0]. Different remainders → return -1. ✓

Edge cases

• All cells already equal: the median is the common value, sum of absolute differences is 0, answer is 0.
• Single cell: answer is always 0.
• x = 1: the feasibility check is trivially passed (everything mod 1 is 0), and the answer is the median-based sum.

Complexity

• Time: O(m·n · log(m·n)) — sort dominates.
• Space: O(m·n) — the flat array.