Minimum Operations to Make a Uni-Value Grid

Medium
1148.

Minimum Operations to Make a Uni-Value Grid

Minimum Operations to Make a Uni-Value Grid is a medium coding problem on arrays, math and sorting, asked in Amazon and Google interviews.

You are given an m x n integer grid and an integer x. In one operation you may add x to, or subtract x from, any single cell.

A grid is uni-value when all its cells hold the same number. Return the minimum number of operations to make the grid uni-value, or -1 if it is impossible.

Example 1

Input
grid = [[1,4],[7,10]], x = 3
Output
4
Explanation
Make every cell 4: one step for 1, one for 7 and two for 10.

Example 2

Input
grid = [[1,2],[3,4]], x = 2
Output
-1
Explanation
Odd and even cells can never meet when every step is 2.

Example 3

Input
grid = [[6]], x = 4
Output
0

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 1 <= x, grid[i][j] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} x
 * @return {number}
 */
var minOperations = function(grid, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make a Uni-Value Grid — Solution

Minimum Operations to Make a Uni-Value Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make a Uni-Value Grid is a medium coding problem on arrays, math and sorting, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Sorting, Matrix
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an m x n integer grid and an integer x. In one operation you may add x to, or subtract x from, any single cell.

A grid is uni-value when all its cells hold the same number. Return the minimum number of operations to make the grid uni-value, or -1 if it is impossible.

Example 1

Input: grid = [[1,4],[7,10]], x = 3
Output: 4
Explanation: Make every cell 4: one step for 1, one for 7 and two for 10.

Example 2

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: Odd and even cells can never meet when every step is 2.

Example 3

Input: grid = [[6]], x = 4
Output: 0

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • 1 <= x, grid[i][j] <= 10^4

Hints for Minimum Operations to Make a Uni-Value Grid

  1. Hint 1

    A cell's value modulo x never changes. What does that say about when the task is possible?

  2. Hint 2

    If every cell has the same remainder, the cost of a target t is the sum of |v - t| / x — a sum of absolute deviations.

  3. Hint 3

    Sum of absolute deviations is minimised at the median. Flatten, sort, and measure against the middle value.

How to solve Minimum Operations to Make a Uni-Value Grid

Steps of size x preserve each value's remainder mod x, so either all remainders match or the task is impossible; when they match, the cheapest common value is the median.

Approach

  1. Flatten the grid into a list of values.
  2. If any value has a different remainder modulo x from the first, return -1.
  3. Sort the values and take the median t = vals[len / 2].
  4. Return the sum of |v - t| / x over all values.

Why it works

Every reachable value for a cell is congruent to it mod x, so a common value exists only if all cells share a remainder; then any value in that class — in particular every grid value — is reachable. The total cost is proportional to the sum of absolute differences from the target, which a median minimises; the median is itself a grid value, so it lies in the right residue class.

Complexity

  • Time — O(k log k) for k = m * n cells
  • Space — O(k)

Pitfalls

  • Checking v % x equal for all cells works only for non-negative values; comparing (v - first) % x == 0 is the robust form.
  • The mean is not the optimal target for absolute differences — the median is.
  • With an even number of cells, either middle value gives the same minimum.

Reference solution

Python

from typing import List

def minOperations(grid: List[List[int]], x: int) -> int:
    vals = sorted(v for row in grid for v in row)
    first = vals[0]
    for v in vals:
        if (v - first) % x != 0:
            return -1
    t = vals[len(vals) // 2]
    return sum(abs(v - t) // x for v in vals)

Java

public static int minOperations(int[][] grid, int x) {
    int k = 0;
    for (int[] row : grid) k += row.length;
    int[] vals = new int[k];
    int idx = 0;
    for (int[] row : grid) for (int v : row) vals[idx++] = v;
    for (int v : vals) if ((v - vals[0]) % x != 0) return -1;
    Arrays.sort(vals);
    int t = vals[k / 2];
    int ops = 0;
    for (int v : vals) ops += Math.abs(v - t) / x;
    return ops;
}

C++

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

JavaScript

var minOperations = function(grid, x) {
    var vals = [];
    for (var r = 0; r < grid.length; r++) {
        for (var c = 0; c < grid[r].length; c++) vals.push(grid[r][c]);
    }
    for (var i = 0; i < vals.length; i++) {
        if ((vals[i] - vals[0]) % x !== 0) return -1;
    }
    vals.sort(function(a, b) { return a - b; });
    var t = vals[Math.floor(vals.length / 2)];
    var ops = 0;
    for (var j = 0; j < vals.length; j++) ops += Math.abs(vals[j] - t) / x;
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms