Minimum Operations to Make a Uni-Value Grid Solution In C++/Python/java/JS
Problem Description
You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.
A uni-value grid is a grid where all the elements of it are equal.
Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.
Example
Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following:
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.
Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.
Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 105
- 1 <= m * n <= 105
- 1 <= x, grid[i][j] <= 104
Figuring out "Minimum Operations to Make a Uni-Value Grid" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!
Optimal Approach
Intuition
We’re given a 2D grid of numbers, and we’re allowed to pick any cell and either add or subtract a fixed number x. We can repeat that as many times as we want, and the goal is to make all the numbers in the grid equal.
The question is:
What's the minimum number of operations to do that?
And is it even possible in the first place?
Let’s Think with an Example First
Let’s take a small and easy grid:
Grid: [[9, 3], [21, 15]]
x = 6
Let’s look at what numbers we have:
[9, 3, 21, 15]
Now think about what we can do:
For example, to change 3 into 9, we can add 6 once.
So:
- 3 → 9 (add 6 once)
- 9 → already 9 (do nothing)
- 15 → 9 (subtract 6 once)
- 21 → 9 (subtract 6 twice)
So in total:
- Add 6 to 3 → 1 op
- Subtract 6 from 15 → 1 op
- Subtract 6 twice from 21 → 2 ops
→ Total: 4 operations
That seems pretty good!
But here's the thing: this example is carefully chosen where all numbers differ from each other by multiples of 6. Like:
- (9 - 3) = 6
- (15 - 9) = 6
- (21 - 15) = 6
In other words, every difference is divisible by x.
So What if They Don’t Differ by a Multiple of x?
Let’s try this:
Grid: [[3, 7], [10, 13]], x = 5
Now our numbers are: [3, 7, 10, 13]
Try changing them all to one number, say 10:
- 3 → ??? (we’d need to add 7, but 7 is not divisible by 5)
- That’s a problem.
So wait… this tells us something important:
We can only move a number in steps of x, right? So unless all numbers can reach each other using steps of x, it’s impossible.
Here’s a way we can think about it:
Every number must have the same remainder modulo x.
Why? Because we’re adding or subtracting multiples of x, which doesn’t change the remainder mod x.
So:
- 3 % 5 = 3
- 7 % 5 = 2 different → Already invalid!
So we stop right here and say not possible — return -1.
That gives us our first insight.
Step 1: Check Modulo Condition
Before doing anything else, we check:
Do all numbers in the grid have the same remainder when divided by x?
If no, return -1.
If yes, then proceed.
Let’s continue with our good example again:
Grid: [[9, 3], [21, 15]]
x = 6
→ All numbers mod 6 = 3
Perfect — we can proceed.
Now Comes the Real Question:
If it is possible to make them all equal, what’s the best target value?
Let’s again look at [9, 3, 21, 15] — which one should we pick to minimize our operations?
Try targeting each value:
- Target 3 → (0, 6, 18, 12) → ops = (0 + 1 + 3 + 2) = 6
- Target 9 → (1, 0, 2, 1) → total = 4
- Target 15 → (1, 2, 0, 1) → total = 4
- Target 21 → (2, 3, 1, 0) → total = 6
Looks like targeting the middle values (9 or 15) gives the least operations.
So what are those values?
They’re the medians of the list!
Insight #2: Choose the Median
We learned from statistics that if we want to minimize the sum of absolute differences from a number, the best number to choose is the median.
That is, for a list of numbers, the total effort to make all numbers the same is minimized when they are converted to the median.
So once we sort our numbers, we can just pick the middle one and aim to convert everything to that value.
Step 2: Flatten and Sort
So we take our grid:
[[9, 3],
[21, 15]]
We flatten it into a list: [9, 3, 21, 15]
Then we sort it: [3, 9, 15, 21]
Now we can clearly see the median — it's either 9 or 15.
And just as we saw earlier, both give us the same minimal total operations: 4.
Step 3: Count Operations
Now that we’ve decided the target (median), we go through every number and see:
How far is it from the median, and how many steps of size x does it take to reach it?
So for each number val:
operations += abs(val - median) / x;
Add them all up, and that’s our answer!
Well summarized! Now, if you think about it, what kind of approach are we using here?
We’re relying on sorting the data and using the statistical power of the median to minimize total steps.
Exactly! This is a smart use of sorting and median, which ensures we get the minimum total operations without checking every target value.
Let's now see how our algorithm looks!
Minimum Operations to Make a Uni-Value Grid Algorithm
- Flatten the 2D grid into a list.
- Check if all numbers mod x are the same — if not, return -1.
- Sort the list, and pick the median.
- Sum up how many x-steps it takes to bring each number to the median.
- Return that total.
Approach
Check Modulo Consistency:
- All elements must have the same remainder when divided by x.
- If any element violates this, it's impossible to make the grid uni-value using the allowed operations.
Flatten and Sort the Grid:
- Convert the 2D grid into a 1D array.
- Sort the array to easily compute the median, which minimizes total steps.
Choose the Median as the Target:
- The median value minimizes the total number of operations (based on absolute differences).
- It’s the optimal target to which we want to convert all elements.
Compute Total Operations:
- For each element, calculate:
abs(value - median) // x
This gives the number of steps needed to convert that element to the median.
Return the Total: The sum of all operations gives the minimum number of steps required.
Dry-Run
Example Input: Grid: [ [12, 6, 18], [0, 12, 24], [6, 18, 12] ], x = 6
Explanation
Step 1: Check Modulo Consistency
We check if every number has the same remainder when divided by x: 12 % 6 = 0
6 % 6 = 0
18 % 6 = 0
0 % 6 = 0
12 % 6 = 0
24 % 6 = 0
6 % 6 = 0
18 % 6 = 0
12 % 6 = 0
Since all values have remainder 0, we can proceed
Step 2: Flatten and Sort the Grid
Flattened grid: [12, 6, 18, 0, 12, 24, 6, 18, 12]
Sorted: [0, 6, 6, 12, 12, 12, 18, 18, 24]
Step 3: Choose the Median
Since there are 9 elements, the median is the 5th element (0-based index 4):
Median = 12
Step 4: Count Operations
We compute how many times we need to add or subtract x to reach 12:
|0 - 12| / 6 = 2
|6 - 12| / 6 = 1
|6 - 12| / 6 = 1
|12 - 12| / 6 = 0
|12 - 12| / 6 = 0
|12 - 12| / 6 = 0
|18 - 12| / 6 = 1
|18 - 12| / 6 = 1
|24 - 12| / 6 = 2
Total operations = 2 + 1 + 1 + 0 + 0 + 0 + 1 + 1 + 2 = 8
Final Answer: 8 operations
Solution
Now let's checkout the "Minimum Operations to Make a Uni-Value Grid code" in C++, Java, Python and JavaScript.
"Minimum Operations to Make a Uni-Value Grid" Code in all Languages.
1. Minimum Operations to Make a Uni-Value Grid solution in C++ Try on Compiler
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
// Flatten the grid into a 1D vector
vector<int> nums;
int mod = grid[0][0] % x;
// Check if all elements have the same remainder mod x
for (auto& row : grid) {
for (int val : row) {
if (val % x != mod) {
return -1;
}
nums.push_back(val);
}
}
// Sort the vector to find the median
sort(nums.begin(), nums.end());
// Get the median element
int median = nums[nums.size() / 2];
int operations = 0;
// Calculate the number of operations for each element to reach the median
for (int val : nums) {
operations += abs(val - median) / x;
}
return operations;
}
};2. Minimum Operations to Make a Uni-Value Grid Solution in Java Try on Compiler
class Solution {
public static int minOperations(int[][] grid, int x) {
// Flatten the 2D grid into 1D array
List<Integer> nums = new ArrayList<>();
int mod = grid[0][0] % x;
// Check mod constraint and fill the list
for (int[] row : grid) {
for (int val : row) {
if (val % x != mod) {
return -1;
}
nums.add(val);
}
}
// Sort the list
Collections.sort(nums);
// Find the median
int median = nums.get(nums.size() / 2);
int operations = 0;
// Calculate total operations needed
for (int val : nums) {
operations += Math.abs(val - median) / x;
}
return operations;
}
}3. Minimum Operations to Make a Uni-Value Grid Solution in Python Try on Compiler
class Solution:
def minOperations(self, grid: List[List[int]], x: int) -> int:
# Flatten the grid into a single list
nums = [val for row in grid for val in row]
# Check if all elements have the same remainder when divided by x
mod = nums[0] % x
if any(val % x != mod for val in nums):
return -1
# Sort the list to find the median
nums.sort()
median = nums[len(nums) // 2]
# Calculate total operations to convert all elements to median
return sum(abs(val - median) // x for val in nums)
4. Minimum Operations to Make a Uni-Value Grid solution in JavaScript Try on Compiler
/**
* @param {number[][]} grid
* @param {number} x
* @return {number}
*/
var minOperations = function(grid, x) {
// Flatten the grid into a 1D array
const nums = [];
for (let row of grid) {
for (let val of row) {
nums.push(val);
}
}
// Check if all elements have the same remainder mod x
const mod = nums[0] % x;
for (let val of nums) {
if (val % x !== mod) {
return -1;
}
}
// Sort the flattened array to find the median
nums.sort((a, b) => a - b);
const median = nums[Math.floor(nums.length / 2)];
// Calculate total operations to make all values equal to median
let operations = 0;
for (let val of nums) {
operations += Math.abs(val - median) / x;
}
return operations;
};Minimum Operations to Make a Uni-Value Grid Complexity Analysis
Time Complexity: O(m × n × log(m × n))
The Rotating and Dropping Stones algorithm involves three key operations:
1. Flattening the grid into a list of stone positions:
→ We iterate through all m × n cells and collect the positions of the stones (1s) into a list. This operation takes O(m × n) time.
2. Sorting the list of stone positions:
→ We sort the collected list based on transformed coordinates (after rotation), to group them efficiently for vertical dropping. This operation takes O(m × n × log(m × n)) time.
3. Simulating the final drop and mapping back to the grid:
→ We iterate through the sorted list and assign new positions to each stone, effectively simulating the "drop". This step also takes O(m × n) time.
Thus, the overall time complexity is:
O(m × n) + O(m × n × log(m × n)) + O(m × n) = O(m × n × log(m × n)),
where m is the number of rows and n is the number of columns.
Space Complexity: O(m x n)
Auxiliary Space Complexity: Auxiliary space refers to the extra space required by the algorithm other than extra space.
- The algorithm uses extra space to store a list of valid flattened values from the grid → O(m × n).
- No additional data structures are used.
- Thus, auxiliary space complexity is: O(m × n).
Total Space Complexity
- Input grid (size m × n): O(m × n)
- Flattened list for processing: O(m × n)
- Variables (constant space) → O(1)
Thus, the total space complexity is O(m × n).
Similar Questions
Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
In one move, you can increment or decrement an element of the array by 1.
Test cases are designed so that the answer will fit in a 32-bit integer.
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.