Minimum Operations to Make a Uni-Value Grid

medium array math sorting median

Problem

You are given an m × n integer grid and an integer x. In one operation you may add x to or subtract x from any single element. Return the minimum number of operations needed to make every element equal, or -1 if it is impossible.

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

Output4

Make every value 6: +x on 2 twice, −x on 8 once, 4→6 once = 4 operations.

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

Output-1

1 and 2 differ by 1, not a multiple of x = 2, so they can never meet.

grid (rows separated by ; values by ,)

x (step size)

def min_operations(grid, x):
    nums = sorted(v for row in grid for v in row)
    rem = nums[0] % x
    for v in nums:
        if v % x != rem:
            return -1
    median = nums[len(nums) // 2]
    ops = 0
    for v in nums:
        ops += abs(v - median) // x
    return ops

function minOperations(grid, x) {
  const nums = grid.flat().sort((a, b) => a - b);
  const rem = nums[0] % x;
  for (const v of nums) {
    if (v % x !== rem) return -1;
  }
  const median = nums[Math.floor(nums.length / 2)];
  let ops = 0;
  for (const v of nums) {
    ops += Math.abs(v - median) / x;
  }
  return ops;
}

int minOperations(int[][] grid, int x) {
    int m = grid.length, n = grid[0].length;
    int[] nums = new int[m * n];
    int k = 0;
    for (int[] row : grid) for (int v : row) nums[k++] = v;
    Arrays.sort(nums);
    int rem = nums[0] % x;
    for (int v : nums) if (v % x != rem) return -1;
    int median = nums[nums.length / 2];
    int ops = 0;
    for (int v : nums) ops += Math.abs(v - median) / x;
    return ops;
}

int minOperations(vector<vector<int>>& grid, int x) {
    vector<int> nums;
    for (auto& row : grid) for (int v : row) nums.push_back(v);
    sort(nums.begin(), nums.end());
    int rem = nums[0] % x;
    for (int v : nums) if (v % x != rem) return -1;
    int median = nums[nums.size() / 2];
    int ops = 0;
    for (int v : nums) ops += abs(v - median) / x;
    return ops;
}

Explanation

Every operation changes an element by exactly ±x, so a value can only ever reach numbers that share its remainder modulo x. For all elements to become equal, they must already agree on that remainder. We flatten the grid and compare each value's v % x against the first one; if any differs, the answer is -1.

When they do all match, the number of operations to turn a value v into a common target t is |v − t| / x (the count of x-sized hops between them). The total cost is the sum of these distances, so we want the target t that minimizes the sum of absolute differences.

That minimizing point is the classic median. Sorting the flattened values and picking the middle one gives an optimal target — pulling it toward either side would increase the distance to more than half the points. We sort, take nums[n/2], and add up |v − median| / x for every value.

Sorting dominates the running time at O(mn · log(mn)); the two linear scans for the remainder check and the cost sum are cheaper. Extra space is the flattened array, O(mn).

Example: grid = [[2,4],[6,8]], x = 2 flattens and sorts to [2,4,6,8], all even (remainder 0). The median is 6, and the costs are 2,1,0,1 for a total of 4 operations.

Time: O(mn · log(mn)) Space: O(mn)