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] <= 104This 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.
C++
Java
Python
C#
JavaScript
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.
Java
Naive complexity could reach O((maxA - minA)/x*m*n) under impractical conditions which are avoided by median heuristic.
| 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. |
Minimum Operations to Make a Uni-Value Grid - Leetcode 2033 - Python • NeetCodeIO • 7,433 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