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 1:
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.
Example 2:
Input: grid = [[1,5],[2,3]], x = 1 Output: 5 Explanation: We can make every element equal to 3.
Example 3:
Input: grid = [[1,2],[3,4]], x = 2 Output: -1 Explanation: It is impossible to make every element equal.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1051 <= x, grid[i][j] <= 104Problem Overview: You are given an m x n grid and an integer x. In one operation, you can add or subtract x from any cell. The goal is to make every value in the grid equal using the minimum number of operations, or return -1 if it cannot be done.
The key observation: since each operation changes a value by exactly x, all numbers must belong to the same remainder group modulo x. If any element differs in value % x, reaching a single common value is impossible.
Approach 1: Heuristic with Median (Flatten + Sorting) (Time: O(mn log(mn)), Space: O(mn))
Flatten the matrix into a 1D array and check that every element has the same remainder when divided by x. If not, return -1 immediately. Otherwise, sort the array and pick the median value as the target.
The median minimizes the sum of absolute differences. For each element v, the number of operations required is |v - median| / x. Add these across all elements to compute the total operations. Sorting ensures you can find the median efficiently, and the absolute distance conversion turns the grid problem into a classic sorting and distance minimization task.
This works because converting all values to the median minimizes the total movement across the array. The approach is simple, deterministic, and performs well for typical grid sizes.
Approach 2: Dynamic Programming with Modulo Analysis (Time: O(mn * k), Space: O(k))
This method focuses on grouping values by the number of steps away from a base remainder class. After confirming that all elements share the same remainder modulo x, convert each value into a normalized step count: (value - base) / x. Now the problem becomes minimizing total moves to convert all step counts into one value.
Instead of sorting, you can build frequency counts of these normalized values and compute the minimum cost using prefix sums or dynamic programming over possible targets. Each transition evaluates how many increments or decrements are required to move elements toward a candidate value.
This technique emphasizes the mathematical structure of the problem and uses properties of arrays and math. While more complex than the median approach, it avoids explicitly sorting the entire dataset and can be useful when working with bounded ranges or precomputed frequencies.
Recommended for interviews: The median-based solution is what interviewers typically expect. It demonstrates that you recognize the modulo feasibility constraint and the median property for minimizing absolute distance. Mentioning the modulo check first shows strong problem insight. Implementing the flattened array + median approach quickly communicates practical algorithm skills.
This approach uses the median for achieving a minimum number of operations. First, we flatten the grid into a 1D list and check if making each element same modulo x throughout the array is possible (i.e., every element should give the same remainder when divided by x). If not, return -1. Once verified, the optimal strategy involves changing each element to the median value since it minimizes the sum of absolute differences.
The code first collects all elements from the grid into a single array. It checks if all elements can be made uniform via x by checking the modulo condition. Then, it sorts the array, calculates the median, and sums up the transformations required to reach this median.
The time complexity is O(m*n*log(m*n)) due to sorting of elements. The space complexity is O(m*n) for storing elements in the flat array.
A dynamic programming approach can be conceived if the uniformity condition across the grid is known, leveraging precomputation of costs to certain potential target values. However, due to the wide range of potential values in the given constraints, this approach degrades to tailor a more heuristic method with optimal modulus checks similar to GCD, discussed earlier. Thus, a full DP-based optimization is often less effective with sheer brute-force modulo checking.
It is not practical to dynamically program solutions when median heuristics offer cost-effective approximations and efficient results within the problem's constraints.
Naive complexity could reach O((maxA - minA)/x*m*n) under impractical conditions which are avoided by median heuristic.
Firstly, to make the grid a single-value grid, the remainder of all elements of the grid with x must be the same.
Therefore, we can first traverse the grid to check whether the remainder of all elements with x is the same. If not, return -1. Otherwise, we put all elements into an array, sort the array, take the median, then traverse the array, calculate the difference between each element and the median, divide it by x, and add all the differences to get the answer.
The time complexity is O((m times n) times log (m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Heuristic with Median | The time complexity is O(m*n*log(m*n)) due to sorting of elements. The space complexity is O(m*n) for storing elements in the flat array. |
| Dynamic Programming with Modulo Analysis | Naive complexity could reach O((maxA - minA)/x*m*n) under impractical conditions which are avoided by median heuristic. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Heuristic with Median (Flatten + Sort) | O(mn log(mn)) | O(mn) | General case; simplest and most common interview solution |
| Dynamic Programming with Modulo Analysis | O(mn * k) | O(k) | Useful when value ranges are bounded or frequency-based optimization is preferred |
Minimum Operations to Make a Uni-Value Grid - Leetcode 2033 - Python • NeetCodeIO • 8,211 views views
Watch 9 more video solutions →Practice Minimum Operations to Make a Uni-Value Grid with our built-in code editor and test cases.
Practice on FleetCode