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.lengthn == grid[i].length1 <= m, n <= 10^51 <= m * n <= 10^51 <= x, grid[i][j] <= 10^4
Hints for Minimum Operations to Make a Uni-Value Grid
Hint 1
A cell's value modulo
xnever changes. What does that say about when the task is possible?Hint 2
If every cell has the same remainder, the cost of a target
tis the sum of|v - t| / x— a sum of absolute deviations.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
- Flatten the grid into a list of values.
- If any value has a different remainder modulo
xfrom the first, return -1. - Sort the values and take the median
t = vals[len / 2]. - Return the sum of
|v - t| / xover 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) fork = m * ncells - Space —
O(k)
Pitfalls
- Checking
v % xequal for all cells works only for non-negative values; comparing(v - first) % x == 0is 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