You are given a 2D integer array grid of size m × n, and an integer k.
In one operation, you can:
k x k submatrix of grid, andReturn the minimum number of operations required to make all elements in the grid equal. If it is not possible, return -1.
A submatrix(x1, y1, x2, y2) is a matrix that forms by choosing all cells matrix[x][y] where x1 <= x <= x2 and y1 <= y <= y2.
Example 1:
Input: grid = [[3,3,5],[3,3,5]], k = 2
Output: 2
Explanation:
Choose the left 2 x 2 submatrix (covering the first two columns) and apply the operation twice.
[[4, 4, 5], [4, 4, 5]][[5, 5, 5], [5, 5, 5]]All elements become equal to 5. Thus, the minimum number of operations is 2.
Example 2:
Input: grid = [[1,2],[2,3]], k = 1
Output: 4
Explanation:
Since k = 1, each operation increments a single cell grid[i][j] by 1. To make all elements equal, the final value must be 3.
grid[0][0] = 1 to 3, requiring 2 operations.grid[0][1] = 2 to 3, requiring 1 operation.grid[1][0] = 2 to 3, requiring 1 operation.Thus, the minimum number of operations is 2 + 1 + 1 + 0 = 4.
Constraints:
1 <= m == grid.length <= 10001 <= n == grid[i].length <= 1000-105 <= grid[i][j] <= 1051 <= k <= min(m, n)Problem Overview: You are given a 2D grid of integers and must determine the minimum number of operations required to make every cell contain the same value. Each operation modifies a range of cells, so the challenge is tracking how previous operations affect future positions while minimizing redundant updates.
Approach 1: Direct Simulation (Brute Force) (Time: O((m*n)^2), Space: O(1))
The most straightforward idea is to repeatedly scan the grid and apply operations whenever a cell differs from the desired target value. For each mismatch, simulate the allowed operation that updates the affected region and propagate the change across the grid. This approach quickly becomes expensive because each operation may touch many cells, and repeated scans multiply the cost. It works only for very small grids and mainly serves as a conceptual baseline.
Approach 2: 2D Difference Array + Greedy (Time: O(m*n), Space: O(m*n))
The efficient solution tracks range updates using a 2D difference array. Instead of directly modifying every cell in a rectangle, record only the boundary adjustments in the difference structure. While iterating the grid from top-left to bottom-right, maintain the cumulative effect of previously applied operations using prefix accumulation. If the current effective value differs from the required value, compute the needed adjustment and greedily apply it starting at that cell. The difference array marks how this operation affects future cells without explicitly updating the entire region.
This greedy traversal works because once you process a cell in row-major order, earlier operations cannot affect it anymore. Each mismatch is fixed immediately, and its impact is propagated efficiently through the difference array. The technique is similar to using prefix sums but extended to two dimensions, which keeps updates constant time while scanning the grid once.
The core idea combines two concepts: fast range updates using a difference matrix and deterministic correction using a greedy scan. Problems involving repeated submatrix updates often benefit from this pattern. If you're unfamiliar with these techniques, review prefix sums, array manipulation, and greedy algorithms.
Recommended for interviews: The 2D Difference Array + Greedy approach is the expected solution. Interviewers want to see that you avoid naive repeated updates and instead track range effects efficiently. Mentioning the brute-force simulation demonstrates understanding of the problem mechanics, but implementing the difference-array optimization shows strong algorithmic maturity.
Since the operation can only increase the value of elements, all elements in the final grid must be equal to some target value T, and T \ge max(grid).
Start traversing the grid from the top-left corner (0, 0). For any position (i, j), if its current value is less than T, since subsequent operations (with a more rightward or downward position as the top-left corner) cannot cover (i, j), it is necessary to perform T - current_val operations at the current position, each using (i, j) as the top-left corner of a k times k increment operation.
If each operation traverses the k times k region, the complexity will reach O(m cdot n cdot k^2). We can use a 2D difference array diff to record the operations. By maintaining the 2D prefix sum of diff in real time, we can obtain the cumulative increment at the current position in O(1) time, and update the future impact of a k times k region in O(1) time.
In most cases, T = max(grid) is sufficient. However, in some cases where k times k regions overlap, a smaller T may cause the middle positions to be passively increased beyond T. According to mathematical consistency, if both T = max(grid) and T = max(grid) + 1 are not feasible, then it is impossible to flatten the grid using k times k operations.
The time complexity is O(m times n) and the space complexity is O(m times n), where m and n are the number of rows and columns of the grid, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation (Brute Force) | O((m*n)^2) | O(1) | Only for very small grids or to understand how operations affect cells |
| 2D Difference Array + Greedy | O(m*n) | O(m*n) | General case with frequent range updates across submatrices |
Practice Minimum Operations to Make All Grid Elements Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor